oj.uz

Submission #1007861

# Submission time Handle Problem Language Result Execution time Memory
1007861 2024-06-25T15:22:14 Z bachhoangxuan Game (IOI13_game) C++17
100 / 100
 2278 ms 107624 KB 
#include "game.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long

int N,M;

int T=0;
struct node{
    ll v=0;
    int p=0,l=0,r=0;
}S[20000005];
struct Segtree{
    int root=0;
    ll update(int l,int r,int &id,int x,ll val){
        if(r<x || x<l) return (id?S[id].v:0);
        if(!id){
            id=++T,S[id].p=x;
            return S[id].v=val;
        }
        if(l==r) return S[id].v=val;
        int mid=(l+r)>>1;
        if(S[id].p) update(l,mid,S[id].l,S[id].p,S[id].v),update(mid+1,r,S[id].r,S[id].p,S[id].v),S[id].p=0;
        return S[id].v=__gcd(update(l,mid,S[id].l,x,val),update(mid+1,r,S[id].r,x,val));
    }
    ll query(int l,int r,int id,int tl,int tr){
        if(tr<l || r<tl || !id) return 0;
        if(tl<=l && r<=tr) return S[id].v;
        if(S[id].p) return ((tl<=S[id].p && S[id].p<=tr)?S[id].v:0);
        int mid=(l+r)>>1;
        return __gcd(query(l,mid,S[id].l,tl,tr),query(mid+1,r,S[id].r,tl,tr));
    };
};

int T2=0;
struct Node{
    Segtree *s;
    int l=0,r=0;
}S2[1000005];
struct Segtree2{
    int root=0;
    ll update(int l,int r,int &id,int x,int y,ll val){
        if(r<x || x<l) return (id?S2[id].s->query(1,M,S2[id].s->root,y,y):0);
        if(!id) S2[id=++T2].s=new Segtree();
        if(l==r){
            S2[id].s->update(1,M,S2[id].s->root,y,val);
            return val;
        }
        int mid=(l+r)>>1;
        val=__gcd(update(l,mid,S2[id].l,x,y,val),update(mid+1,r,S2[id].r,x,y,val));
        S2[id].s->update(1,M,S2[id].s->root,y,val);
        return val;
    }
    ll query(int l,int r,int id,int x,int y,int u,int v){
        if(r<x || u<l || !id) return 0;
        if(x<=l && r<=u) return S2[id].s->query(1,M,S2[id].s->root,y,v);
        int mid=(l+r)>>1;
        return __gcd(query(l,mid,S2[id].l,x,y,u,v),query(mid+1,r,S2[id].r,x,y,u,v));
    }
}ST;

void init(int _N,int _M){
    N=_N;M=_M;
}

void update(int P, int Q, ll K) {
    P++;Q++;
    ST.update(1,N,ST.root,P,Q,K);
}

ll calculate(int P, int Q, int U, int V) {
    P++;Q++;U++;V++;
    return ST.query(1,N,ST.root,P,Q,U,V);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16984 KB Output is correct
2 Correct 2 ms 16988 KB Output is correct
3 Correct 2 ms 16988 KB Output is correct
4 Correct 2 ms 16988 KB Output is correct
5 Correct 2 ms 16988 KB Output is correct
6 Correct 2 ms 16988 KB Output is correct
7 Correct 2 ms 16988 KB Output is correct
8 Correct 2 ms 16988 KB Output is correct
9 Correct 2 ms 17012 KB Output is correct
10 Correct 2 ms 17236 KB Output is correct
11 Correct 2 ms 16988 KB Output is correct
12 Correct 2 ms 16988 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16984 KB Output is correct
2 Correct 2 ms 16988 KB Output is correct
3 Correct 2 ms 16988 KB Output is correct
4 Correct 256 ms 25492 KB Output is correct
5 Correct 186 ms 25680 KB Output is correct
6 Correct 239 ms 22612 KB Output is correct
7 Correct 257 ms 21848 KB Output is correct
8 Correct 196 ms 22872 KB Output is correct
9 Correct 257 ms 22316 KB Output is correct
10 Correct 238 ms 21896 KB Output is correct
11 Correct 2 ms 16984 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16988 KB Output is correct
2 Correct 2 ms 17020 KB Output is correct
3 Correct 2 ms 16988 KB Output is correct
4 Correct 2 ms 16988 KB Output is correct
5 Correct 2 ms 16988 KB Output is correct
6 Correct 2 ms 17012 KB Output is correct
7 Correct 2 ms 16984 KB Output is correct
8 Correct 3 ms 16988 KB Output is correct
9 Correct 2 ms 16984 KB Output is correct
10 Correct 2 ms 16988 KB Output is correct
11 Correct 2 ms 17028 KB Output is correct
12 Correct 395 ms 27536 KB Output is correct
13 Correct 664 ms 22096 KB Output is correct
14 Correct 155 ms 20048 KB Output is correct
15 Correct 738 ms 24364 KB Output is correct
16 Correct 99 ms 26328 KB Output is correct
17 Correct 407 ms 23040 KB Output is correct
18 Correct 559 ms 27144 KB Output is correct
19 Correct 524 ms 27216 KB Output is correct
20 Correct 493 ms 26704 KB Output is correct
21 Correct 2 ms 16988 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16988 KB Output is correct
2 Correct 2 ms 16988 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 2 ms 17036 KB Output is correct
5 Correct 2 ms 16988 KB Output is correct
6 Correct 3 ms 16988 KB Output is correct
7 Correct 2 ms 16988 KB Output is correct
8 Correct 2 ms 16988 KB Output is correct
9 Correct 2 ms 16988 KB Output is correct
10 Correct 2 ms 16988 KB Output is correct
11 Correct 2 ms 16988 KB Output is correct
12 Correct 263 ms 25428 KB Output is correct
13 Correct 171 ms 25680 KB Output is correct
14 Correct 243 ms 22612 KB Output is correct
15 Correct 248 ms 21912 KB Output is correct
16 Correct 184 ms 22868 KB Output is correct
17 Correct 256 ms 22380 KB Output is correct
18 Correct 221 ms 22108 KB Output is correct
19 Correct 389 ms 27460 KB Output is correct
20 Correct 616 ms 22100 KB Output is correct
21 Correct 156 ms 20048 KB Output is correct
22 Correct 727 ms 24404 KB Output is correct
23 Correct 119 ms 26320 KB Output is correct
24 Correct 394 ms 23124 KB Output is correct
25 Correct 566 ms 26960 KB Output is correct
26 Correct 531 ms 27312 KB Output is correct
27 Correct 465 ms 26536 KB Output is correct
28 Correct 250 ms 44988 KB Output is correct
29 Correct 555 ms 43856 KB Output is correct
30 Correct 1883 ms 40784 KB Output is correct
31 Correct 1817 ms 60860 KB Output is correct
32 Correct 286 ms 22352 KB Output is correct
33 Correct 403 ms 24456 KB Output is correct
34 Correct 128 ms 38996 KB Output is correct
35 Correct 493 ms 32448 KB Output is correct
36 Correct 762 ms 41548 KB Output is correct
37 Correct 680 ms 41556 KB Output is correct
38 Correct 698 ms 41000 KB Output is correct
39 Correct 556 ms 35820 KB Output is correct
40 Correct 2 ms 16984 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16988 KB Output is correct
2 Correct 2 ms 16988 KB Output is correct
3 Correct 2 ms 16992 KB Output is correct
4 Correct 2 ms 16988 KB Output is correct
5 Correct 2 ms 16988 KB Output is correct
6 Correct 3 ms 16988 KB Output is correct
7 Correct 2 ms 17244 KB Output is correct
8 Correct 2 ms 16988 KB Output is correct
9 Correct 2 ms 16988 KB Output is correct
10 Correct 2 ms 16988 KB Output is correct
11 Correct 2 ms 16988 KB Output is correct
12 Correct 250 ms 25488 KB Output is correct
13 Correct 179 ms 25644 KB Output is correct
14 Correct 238 ms 22464 KB Output is correct
15 Correct 272 ms 21844 KB Output is correct
16 Correct 184 ms 22864 KB Output is correct
17 Correct 285 ms 22472 KB Output is correct
18 Correct 237 ms 22100 KB Output is correct
19 Correct 432 ms 27472 KB Output is correct
20 Correct 680 ms 22100 KB Output is correct
21 Correct 145 ms 19904 KB Output is correct
22 Correct 836 ms 24336 KB Output is correct
23 Correct 120 ms 26264 KB Output is correct
24 Correct 426 ms 22868 KB Output is correct
25 Correct 609 ms 27092 KB Output is correct
26 Correct 534 ms 27216 KB Output is correct
27 Correct 453 ms 26464 KB Output is correct
28 Correct 255 ms 45196 KB Output is correct
29 Correct 574 ms 43668 KB Output is correct
30 Correct 1827 ms 40700 KB Output is correct
31 Correct 1765 ms 60692 KB Output is correct
32 Correct 269 ms 22344 KB Output is correct
33 Correct 377 ms 24408 KB Output is correct
34 Correct 126 ms 39048 KB Output is correct
35 Correct 448 ms 32340 KB Output is correct
36 Correct 696 ms 39120 KB Output is correct
37 Correct 629 ms 36180 KB Output is correct
38 Correct 617 ms 35408 KB Output is correct
39 Correct 350 ms 76528 KB Output is correct
40 Correct 844 ms 68176 KB Output is correct
41 Correct 2237 ms 68048 KB Output is correct
42 Correct 2278 ms 107624 KB Output is correct
43 Correct 215 ms 62924 KB Output is correct
44 Correct 399 ms 27120 KB Output is correct
45 Correct 573 ms 40816 KB Output is correct
46 Correct 905 ms 67084 KB Output is correct
47 Correct 884 ms 66956 KB Output is correct
48 Correct 856 ms 66644 KB Output is correct
49 Correct 2 ms 16988 KB Output is correct