Submission #5991291

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const int INF=1e9;

int t[400000],m;

void init(int n){
    m=1;
    while(m<n)m*=2;
    for(int i=0;i<2*m-1;i++)t[i]=-1;
}

void update(int k,int a){
    k+=m-1;
    t[k]=a;
    while(k>0){
        k=(k-1)/2;
        t[k]=min(t[2*k+1],t[2*k+2]);
    }
}

int query(int a,int b,int k,int l,int r){
    if(b<=l||r<=a)return INF;
    if(a<=l&&r<=b)return t[k];
    return min(query(a,b,2*k+1,l,(l+r)/2),query(a,b,2*k+2,(l+r)/2,r));
}

int main(){
    int n;
    cin>>n;
    int c[n],a[n];
    c[0]=a[0]=0;
    for(int i=1;i<n;i++){
        cin>>c[i]>>a[i];
    }
    init(n);
    int grundy[n];
    for(int i=0;i<n;i++){
        if(t[m-1]<i-c[i]){
            grundy[i]=0;
        }
        else{
            int ok=0,ng=n;
            while(abs(ok-ng)>1){
                int mid=(ok+ng)/2;
                if(i-c[i]<=query(0,mid+1,0,0,m)){
                    ok=mid;
                }else{
                    ng=mid;
                }
            }
            grundy[i]=ng;
        }
        update(grundy[i],i);
    }
    int ans=0;
    for(int i=1;i<n;i++){
        if(a[i]&1){
            ans^=grundy[i];
        }
    }
    if(ans){
        cout<<"First"<<endl;
    }else{
        cout<<"Second"<<endl;
    }
}

Submission Info

Judge Result