oj.uz

Submission #1102580

# Submission time Handle Problem Language Result Execution time Memory
1102580 2024-10-18T11:11:41 Z ttamx Game (IOI13_game) C++17
80 / 100
 2520 ms 256000 KB 
#include "game.h"
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

ll gcd2(ll X,ll Y){
    while(Y!=0)tie(X,Y)=make_pair(Y,X%Y);
    return X;
}

int n,m;

struct Node{
    ll val;
    int l,r;
    Node():val(0LL),l(0),r(0){}
}node[10000000];

int cur_node=0;

struct SegTree{
    int root;
    SegTree():root(0){}
    ll get(int t){
        return t?node[t].val:0LL;
    }
    void modify(int l,int r,int &t,int x,ll v){
        if(!t)t=++cur_node;
        if(l==r)return void(node[t].val=v);
        int m=(l+r)/2;
        if(x<=m)modify(l,m,node[t].l,x,v);
        else modify(m+1,r,node[t].r,x,v);
        node[t].val=gcd2(get(node[t].l),get(node[t].r));
    }
    void modify(int x,ll v){
        modify(0,m-1,root,x,v);
    }
    ll query(int l,int r,int &t,int x,int y){
        if(y<l||r<x||!t)return 0LL;
        if(x<=l&&r<=y)return node[t].val;
        int m=(l+r)/2;
        return gcd2(query(l,m,node[t].l,x,y),query(m+1,r,node[t].r,x,y));
    }
    ll query(int x,int y){
        return query(0,m-1,root,x,y);
    }
};

struct SegTree2D{
    struct Node{
        SegTree tree;
        int l,r;
        Node():tree(),l(),r(){}
    }node[800000];
    int root,cur_node;
    SegTree2D():root(0),cur_node(0){}
    ll get(int t,int x){
        return t?node[t].tree.query(x,x):0LL;
    }
    void modify(int l,int r,int &t,int x,int y,ll v){
        if(!t)t=++cur_node;
        if(l<r){
            int m=(l+r)/2;
            if(x<=m)modify(l,m,node[t].l,x,y,v);
            else modify(m+1,r,node[t].r,x,y,v);
            v=gcd2(get(node[t].l,y),get(node[t].r,y));
        }
        node[t].tree.modify(y,v);
    }
    void modify(int x,int y,ll v){
        modify(0,n-1,root,x,y,v);
    }
    ll query(int l,int r,int &t,int x,int y,int x2,int y2){
        if(y<l||r<x||!t)return 0LL;
        if(x<=l&&r<=y)return node[t].tree.query(x2,y2);
        int m=(l+r)/2;
        return gcd2(query(l,m,node[t].l,x,y,x2,y2),query(m+1,r,node[t].r,x,y,x2,y2));
    }
    ll query(int x,int y,int x2,int y2){
        return query(0,n-1,root,x,y,x2,y2);
    }
}seg;

void init(int R,int C){
    n=R,m=C;
}

void update(int P,int Q,ll K){
    seg.modify(P,Q,K);
}

ll calculate(int P,int Q,int U,int V){
    return seg.query(P,U,Q,V);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 166224 KB Output is correct
2 Correct 23 ms 166224 KB Output is correct
3 Correct 25 ms 166264 KB Output is correct
4 Correct 23 ms 166372 KB Output is correct
5 Correct 23 ms 166224 KB Output is correct
6 Correct 26 ms 166216 KB Output is correct
7 Correct 24 ms 166224 KB Output is correct
8 Correct 23 ms 166196 KB Output is correct
9 Correct 23 ms 166220 KB Output is correct
10 Correct 24 ms 166240 KB Output is correct
11 Correct 24 ms 166224 KB Output is correct
12 Correct 25 ms 166392 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 166224 KB Output is correct
2 Correct 21 ms 166140 KB Output is correct
3 Correct 21 ms 166224 KB Output is correct
4 Correct 320 ms 170344 KB Output is correct
5 Correct 220 ms 170568 KB Output is correct
6 Correct 293 ms 167240 KB Output is correct
7 Correct 299 ms 167148 KB Output is correct
8 Correct 220 ms 167752 KB Output is correct
9 Correct 291 ms 167240 KB Output is correct
10 Correct 276 ms 166896 KB Output is correct
11 Correct 24 ms 166224 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 166172 KB Output is correct
2 Correct 25 ms 166224 KB Output is correct
3 Correct 25 ms 166332 KB Output is correct
4 Correct 22 ms 166224 KB Output is correct
5 Correct 23 ms 166224 KB Output is correct
6 Correct 21 ms 166392 KB Output is correct
7 Correct 24 ms 166224 KB Output is correct
8 Correct 21 ms 166220 KB Output is correct
9 Correct 24 ms 166184 KB Output is correct
10 Correct 24 ms 166216 KB Output is correct
11 Correct 24 ms 166224 KB Output is correct
12 Correct 521 ms 170312 KB Output is correct
13 Correct 785 ms 166864 KB Output is correct
14 Correct 199 ms 166728 KB Output is correct
15 Correct 899 ms 166980 KB Output is correct
16 Correct 145 ms 166892 KB Output is correct
17 Correct 499 ms 167496 KB Output is correct
18 Correct 788 ms 167216 KB Output is correct
19 Correct 666 ms 167364 KB Output is correct
20 Correct 578 ms 166984 KB Output is correct
21 Correct 21 ms 166224 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 166392 KB Output is correct
2 Correct 22 ms 166224 KB Output is correct
3 Correct 22 ms 166224 KB Output is correct
4 Correct 21 ms 166356 KB Output is correct
5 Correct 21 ms 166224 KB Output is correct
6 Correct 21 ms 166224 KB Output is correct
7 Correct 22 ms 166224 KB Output is correct
8 Correct 23 ms 166356 KB Output is correct
9 Correct 22 ms 166228 KB Output is correct
10 Correct 21 ms 166236 KB Output is correct
11 Correct 21 ms 166224 KB Output is correct
12 Correct 345 ms 170312 KB Output is correct
13 Correct 247 ms 170568 KB Output is correct
14 Correct 288 ms 167240 KB Output is correct
15 Correct 324 ms 166984 KB Output is correct
16 Correct 233 ms 167880 KB Output is correct
17 Correct 315 ms 167240 KB Output is correct
18 Correct 294 ms 166868 KB Output is correct
19 Correct 533 ms 170400 KB Output is correct
20 Correct 771 ms 166948 KB Output is correct
21 Correct 198 ms 166728 KB Output is correct
22 Correct 902 ms 167044 KB Output is correct
23 Correct 149 ms 166984 KB Output is correct
24 Correct 482 ms 167496 KB Output is correct
25 Correct 676 ms 167240 KB Output is correct
26 Correct 601 ms 167496 KB Output is correct
27 Correct 567 ms 166984 KB Output is correct
28 Correct 343 ms 166744 KB Output is correct
29 Correct 854 ms 169932 KB Output is correct
30 Correct 2520 ms 166648 KB Output is correct
31 Correct 2374 ms 166976 KB Output is correct
32 Correct 369 ms 166728 KB Output is correct
33 Correct 494 ms 166700 KB Output is correct
34 Correct 233 ms 166984 KB Output is correct
35 Correct 611 ms 167496 KB Output is correct
36 Correct 1062 ms 167240 KB Output is correct
37 Correct 980 ms 167500 KB Output is correct
38 Correct 908 ms 166944 KB Output is correct
39 Correct 844 ms 167668 KB Output is correct
40 Correct 27 ms 166224 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 166348 KB Output is correct
2 Correct 23 ms 166224 KB Output is correct
3 Correct 24 ms 166204 KB Output is correct
4 Correct 22 ms 166224 KB Output is correct
5 Correct 24 ms 166220 KB Output is correct
6 Correct 23 ms 166356 KB Output is correct
7 Correct 24 ms 166224 KB Output is correct
8 Correct 24 ms 166224 KB Output is correct
9 Correct 24 ms 166368 KB Output is correct
10 Correct 24 ms 166224 KB Output is correct
11 Correct 27 ms 166368 KB Output is correct
12 Correct 341 ms 170400 KB Output is correct
13 Correct 232 ms 170568 KB Output is correct
14 Correct 298 ms 167240 KB Output is correct
15 Correct 375 ms 166984 KB Output is correct
16 Correct 239 ms 167752 KB Output is correct
17 Correct 314 ms 167264 KB Output is correct
18 Correct 271 ms 166892 KB Output is correct
19 Correct 553 ms 170312 KB Output is correct
20 Correct 746 ms 166984 KB Output is correct
21 Correct 188 ms 166828 KB Output is correct
22 Correct 888 ms 166888 KB Output is correct
23 Correct 146 ms 166984 KB Output is correct
24 Correct 521 ms 167468 KB Output is correct
25 Correct 730 ms 167240 KB Output is correct
26 Correct 698 ms 167472 KB Output is correct
27 Correct 620 ms 166984 KB Output is correct
28 Correct 364 ms 166728 KB Output is correct
29 Correct 868 ms 169800 KB Output is correct
30 Correct 2482 ms 166792 KB Output is correct
31 Correct 2310 ms 167012 KB Output is correct
32 Correct 364 ms 166728 KB Output is correct
33 Correct 462 ms 166720 KB Output is correct
34 Correct 247 ms 166888 KB Output is correct
35 Correct 641 ms 167496 KB Output is correct
36 Correct 1142 ms 167248 KB Output is correct
37 Correct 896 ms 167504 KB Output is correct
38 Correct 928 ms 166984 KB Output is correct
39 Runtime error 665 ms 256000 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -