oj.uz

답안 #218535

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
218535 2020-04-02T09:02:45 Z urd05 게임 (IOI13_game) C++14
80 / 100
 3273 ms 256004 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;
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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 7 ms 640 KB Output is correct
3 Correct 7 ms 640 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 10 ms 640 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 6 ms 640 KB Output is correct
10 Correct 6 ms 512 KB Output is correct
11 Correct 6 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 1016 ms 33344 KB Output is correct
5 Correct 841 ms 33456 KB Output is correct
6 Correct 939 ms 30572 KB Output is correct
7 Correct 967 ms 30784 KB Output is correct
8 Correct 613 ms 20828 KB Output is correct
9 Correct 971 ms 30572 KB Output is correct
10 Correct 898 ms 30056 KB Output is correct
11 Correct 5 ms 384 KB Output is correct

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 7 ms 640 KB Output is correct
3 Correct 7 ms 640 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 7 ms 640 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 6 ms 640 KB Output is correct
10 Correct 6 ms 512 KB Output is correct
11 Correct 6 ms 384 KB Output is correct
12 Correct 1525 ms 18792 KB Output is correct
13 Correct 2037 ms 10592 KB Output is correct
14 Correct 614 ms 6008 KB Output is correct
15 Correct 2224 ms 13836 KB Output is correct
16 Correct 802 ms 21112 KB Output is correct
17 Correct 1167 ms 16632 KB Output is correct
18 Correct 1715 ms 22544 KB Output is correct
19 Correct 1568 ms 22520 KB Output is correct
20 Correct 1491 ms 22004 KB Output is correct
21 Correct 5 ms 384 KB Output is correct

Subtask #4
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 8 ms 640 KB Output is correct
3 Correct 7 ms 640 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 7 ms 640 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 6 ms 640 KB Output is correct
10 Correct 5 ms 512 KB Output is correct
11 Correct 6 ms 384 KB Output is correct
12 Correct 915 ms 33476 KB Output is correct
13 Correct 773 ms 33276 KB Output is correct
14 Correct 948 ms 30576 KB Output is correct
15 Correct 927 ms 30740 KB Output is correct
16 Correct 632 ms 20880 KB Output is correct
17 Correct 994 ms 30652 KB Output is correct
18 Correct 865 ms 29980 KB Output is correct
19 Correct 1524 ms 18680 KB Output is correct
20 Correct 2005 ms 10616 KB Output is correct
21 Correct 657 ms 6008 KB Output is correct
22 Correct 2223 ms 13872 KB Output is correct
23 Correct 778 ms 20984 KB Output is correct
24 Correct 1098 ms 16656 KB Output is correct
25 Correct 1675 ms 22600 KB Output is correct
26 Correct 1553 ms 22520 KB Output is correct
27 Correct 1480 ms 22136 KB Output is correct
28 Correct 891 ms 157252 KB Output is correct
29 Correct 1722 ms 173360 KB Output is correct
30 Correct 3238 ms 125512 KB Output is correct
31 Correct 3024 ms 102224 KB Output is correct
32 Correct 523 ms 10488 KB Output is correct
33 Correct 715 ms 12664 KB Output is correct
34 Correct 963 ms 166920 KB Output is correct
35 Correct 1233 ms 91340 KB Output is correct
36 Correct 2232 ms 171204 KB Output is correct
37 Correct 1971 ms 171336 KB Output is correct
38 Correct 1985 ms 170960 KB Output is correct
39 Correct 1663 ms 134140 KB Output is correct
40 Correct 5 ms 384 KB Output is correct

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 7 ms 640 KB Output is correct
3 Correct 7 ms 640 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 6 ms 640 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 6 ms 640 KB Output is correct
10 Correct 6 ms 512 KB Output is correct
11 Correct 6 ms 384 KB Output is correct
12 Correct 994 ms 33504 KB Output is correct
13 Correct 879 ms 33264 KB Output is correct
14 Correct 972 ms 30840 KB Output is correct
15 Correct 982 ms 30964 KB Output is correct
16 Correct 652 ms 20828 KB Output is correct
17 Correct 967 ms 30624 KB Output is correct
18 Correct 925 ms 30200 KB Output is correct
19 Correct 1579 ms 18664 KB Output is correct
20 Correct 2118 ms 10436 KB Output is correct
21 Correct 642 ms 5880 KB Output is correct
22 Correct 2202 ms 13824 KB Output is correct
23 Correct 795 ms 20984 KB Output is correct
24 Correct 1120 ms 16632 KB Output is correct
25 Correct 1735 ms 22456 KB Output is correct
26 Correct 1627 ms 22776 KB Output is correct
27 Correct 1493 ms 21880 KB Output is correct
28 Correct 915 ms 156996 KB Output is correct
29 Correct 1736 ms 173536 KB Output is correct
30 Correct 3273 ms 125428 KB Output is correct
31 Correct 3071 ms 102392 KB Output is correct
32 Correct 526 ms 10488 KB Output is correct
33 Correct 717 ms 12808 KB Output is correct
34 Correct 973 ms 167072 KB Output is correct
35 Correct 1253 ms 91472 KB Output is correct
36 Correct 2263 ms 171208 KB Output is correct
37 Correct 2160 ms 170984 KB Output is correct
38 Correct 2173 ms 170720 KB Output is correct
39 Runtime error 1230 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -