oj.uz

Submission #218492

# Submission time Handle Problem Language Result Execution time Memory
218492 2020-04-02T08:17:52 Z urd05 Game (IOI13_game) C++14
0 / 100
 5 ms 384 KB 
#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;

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=c-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=c-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.push_back({st,-1,-1});
    }
    void update(int x,int y,long long v,int node=0,int nodel=0,int noder=r-1) {
        if (nodel==noder) {
            seg[node].st.update(y,v);
            return;
        }
        int mid=(nodel+noder)/2;
        seg[node].st.update(y,v);
        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 sum(int xl,int xr,int yl,int yr,int node=0,int nodel=0,int noder=r-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

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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Incorrect 5 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 5 ms 256 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Incorrect 5 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Incorrect 5 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 5 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -