Submission #218535

#	Time	Username	Problem	Language	Result	Execution time	Memory
218535		urd05	Game (IOI13_game)	C++14	80 / 100	3273 ms	256004 KiB

game

#include <bits/stdc++.h>
#include "game.h"
using namespace std;

typedef pair<int,int> P;
typedef pair<int,P> iP;
typedef pair<P,P> PP;
int r,c;
const int sz=1<<30;

long long gcd(long long a,long long b) {
    if (b==0) {
        return a;
    }
    return gcd(b,a%b);
}

struct Node {
    long long val;
    int l,r;
};

struct DynamicSegmentTree {
    vector<Node> seg;
    void init() {
        seg.push_back({0,-1,-1});
    }
    void update(int y,long long v,int node=0,int nodel=0,int noder=sz-1) {
        if (nodel==noder) {
            seg[node].val=v;
            return;
        }
        int mid=(nodel+noder)/2;
        if (y<=mid) {
            if (seg[node].l==-1) {
                seg[node].l=seg.size();
                seg.push_back({0,-1,-1});
            }
            update(y,v,seg[node].l,nodel,mid);
        }
        else {
            if (seg[node].r==-1) {
                seg[node].r=seg.size();
                seg.push_back({0,-1,-1});
            }
            update(y,v,seg[node].r,mid+1,noder);
        }
        seg[node].val=0;
        if (seg[node].l!=-1) {
            seg[node].val=gcd(seg[node].val,seg[seg[node].l].val);
        }
        if (seg[node].r!=-1) {
            seg[node].val=gcd(seg[node].val,seg[seg[node].r].val);
        }
    }
    long long sum(int l,int r,int node=0,int nodel=0,int noder=sz-1) {
        if (r<nodel||l>noder) {
            return 0;
        }
        if (l<=nodel&&noder<=r) {
            return seg[node].val;
        }
        long long ret=0;
        int mid=(nodel+noder)/2;
        if (seg[node].l!=-1) {
            ret=gcd(sum(l,r,seg[node].l,nodel,mid),ret);
        }
        if (seg[node].r!=-1) {
            ret=gcd(sum(l,r,seg[node].r,mid+1,noder),ret);
        }
        return ret;
    }
};

struct oneDNode {
    DynamicSegmentTree st;
    int l,r;
};

struct twoDDynamicSegmentTree {
    vector<oneDNode> seg;
    void init() {
        DynamicSegmentTree st;
        st.init();
        seg.reserve(1000000);
        seg.push_back({st,-1,-1});
    }
    void update(int x,int y,long long v,int node=0,int nodel=0,int noder=sz-1) {
        if (nodel==noder) {
            seg[node].st.update(y,v);
            return;
        }
        int mid=(nodel+noder)/2;
        if (x<=mid) {
            if (seg[node].l==-1) {
                seg[node].l=seg.size();
                DynamicSegmentTree st;
                st.init();
                seg.push_back({st,-1,-1});
            }
            update(x,y,v,seg[node].l,nodel,mid);
        }
        else {
            if (seg[node].r==-1) {
                seg[node].r=seg.size();
                DynamicSegmentTree st;
                st.init();
                seg.push_back({st,-1,-1});
            }
            update(x,y,v,seg[node].r,mid+1,noder);
        }
        long long val=0;
        if (seg[node].l!=-1) {
            val=gcd(seg[seg[node].l].st.sum(y,y),val);
        }
        if (seg[node].r!=-1) {
            val=gcd(seg[seg[node].r].st.sum(y,y),val);
        }
        seg[node].st.update(y,val);
    }
    long long sum(int xl,int xr,int yl,int yr,int node=0,int nodel=0,int noder=sz-1) {
        if (xr<nodel||xl>noder) {
            return 0;
        }
        if (xl<=nodel&&noder<=xr) {
            return seg[node].st.sum(yl,yr);
        }
        int mid=(nodel+noder)/2;
        long long ret=0;
        if (seg[node].l!=-1) {
            ret=gcd(ret,sum(xl,xr,yl,yr,seg[node].l,nodel,mid));
        }
        if (seg[node].r!=-1) {
            ret=gcd(ret,sum(xl,xr,yl,yr,seg[node].r,mid+1,noder));
        }
        return ret;
    }
};

twoDDynamicSegmentTree st;

void init(int x,int y) {
    r=x;
    c=y;
    st.init();
}

void update(int p,int q,long long k) {
    st.update(p,q,k);
}

long long calculate(int p,int q,int u,int v) {
    return st.sum(p,u,q,v);
}

Compilation message (stderr)

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 17 / 17
• Subtask 5: 0 / 20