oj.uz

Submission #384159

# Submission time Handle Problem Language Result Execution time Memory
384159 2021-03-31T15:13:28 Z alishahali1382 Game (IOI13_game) C++14
80 / 100
 4570 ms 256004 KB 
#include "game.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define debug(x) {cerr<<#x<<"="<<x<<"\n";}
#define debug2(x, y) {cerr<<#x<<", "<<#y<<" = "<<x<<", "<<y<<"\n";}
#define debugp(p) {cerr<<#p" = {"<<p.first<<", "<<p.second<<"}\n";}
#define pb push_back
#define all(x) x.begin(), x.end()

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

const int SEGSZ=20000000, SEGSZ2=1000000;

ll seg[SEGSZ], ans;
int L[SEGSZ], R[SEGSZ], ts;
int Set(int id, int tl, int tr, int pos, ll val){
    if (!id) id=++ts;
    if (tr-tl==1){
        seg[id]=val;
        return id;
    }
    int mid=(tl+tr)>>1;
    if (pos<mid) L[id]=Set(L[id], tl, mid, pos, val);
    else R[id]=Set(R[id], mid, tr, pos, val);
    seg[id]=gcd2(seg[L[id]], seg[R[id]]);
    return id;
}
void Get(int id, int tl, int tr, int l, int r, ll &ans){
    if (r<=tl || tr<=l || !id) return ;
    if (l<=tl && tr<=r){
        // debug(seg[id])
        ans=gcd2(ans, seg[id]); // overall log(10^18) for single query of problem
        return ;
    }
    int mid=(tl+tr)>>1;
    Get(L[id], tl, mid, l, r, ans);
    Get(R[id], mid, tr, l, r, ans);
}

int n, m, root;
int seg2[SEGSZ2], L2[SEGSZ2], R2[SEGSZ2], ts2;
int Set2(int id, int tl, int tr, int x, int y, ll val){
    if (!id) id=++ts2;
    // cerr<<"update "<<val<<" in "<<tl<<" "<<tr<<"\n";
    if (tr-tl==1) {
        seg2[id]=Set(seg2[id], 0, m, y, val);
        return id;
    }
    int mid=(tl+tr)>>1;
    if (x<mid) L2[id]=Set2(L2[id], tl, mid, x, y, val);
    else R2[id]=Set2(R2[id], mid, tr, x, y, val);
    // debug2(L2[id], R2[id])
    // debug2(seg[seg2[L2[id]]], seg[seg2[R2[id]]])
    ll res=0;
    Get(seg2[L2[id]], 0, m, y, y+1, res);
    Get(seg2[R2[id]], 0, m, y, y+1, res);
    // debug(res)
    seg2[id]=Set(seg2[id], 0, m, y, res);
    return id;
}
void Get2(int id, int tl, int tr, int l1, int l2, int r1, int r2){
    if (r1<=tl || tr<=l1 || !id) return ;
    if (l1<=tl && tr<=r1){
        // debug2(tl, tr)
        Get(seg2[id], 0, m, l2, r2, ans);
        return ;
    }
    int mid=(tl+tr)>>1;
    Get2(L2[id], tl, mid, l1, l2, r1, r2);
    Get2(R2[id], mid, tr, l1, l2, r1, r2);
}

void init(int nn, int mm) {
    n=nn;
    m=mm;
}

void update(int P, int Q, ll K) {
    root=Set2(root, 0, n, P, Q, K);
}

ll calculate(int P, int Q, int U, int V) {
    ans=0;
    Get2(root, 0, n, P, Q, U+1, V+1);
    return ans;
}
/*
3 3 4
2 0 1 2 2
1 1 0 13
1 2 2 1
2 0 0 2 2

*/

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 577 ms 8808 KB Output is correct
5 Correct 447 ms 9068 KB Output is correct
6 Correct 428 ms 5868 KB Output is correct
7 Correct 482 ms 5612 KB Output is correct
8 Correct 331 ms 4716 KB Output is correct
9 Correct 457 ms 5756 KB Output is correct
10 Correct 431 ms 5228 KB Output is correct
11 Correct 1 ms 364 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 991 ms 10476 KB Output is correct
13 Correct 1413 ms 3852 KB Output is correct
14 Correct 299 ms 1200 KB Output is correct
15 Correct 1682 ms 5164 KB Output is correct
16 Correct 236 ms 9856 KB Output is correct
17 Correct 674 ms 6796 KB Output is correct
18 Correct 1198 ms 10092 KB Output is correct
19 Correct 979 ms 10348 KB Output is correct
20 Correct 990 ms 9836 KB Output is correct
21 Correct 1 ms 364 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 570 ms 8812 KB Output is correct
13 Correct 428 ms 9196 KB Output is correct
14 Correct 419 ms 5868 KB Output is correct
15 Correct 468 ms 5612 KB Output is correct
16 Correct 328 ms 4460 KB Output is correct
17 Correct 442 ms 5612 KB Output is correct
18 Correct 422 ms 5516 KB Output is correct
19 Correct 983 ms 10476 KB Output is correct
20 Correct 1436 ms 3820 KB Output is correct
21 Correct 296 ms 1132 KB Output is correct
22 Correct 1685 ms 5140 KB Output is correct
23 Correct 227 ms 9900 KB Output is correct
24 Correct 668 ms 6796 KB Output is correct
25 Correct 1292 ms 10356 KB Output is correct
26 Correct 1127 ms 10348 KB Output is correct
27 Correct 1068 ms 9760 KB Output is correct
28 Correct 834 ms 126828 KB Output is correct
29 Correct 2273 ms 150972 KB Output is correct
30 Correct 4570 ms 109028 KB Output is correct
31 Correct 4285 ms 84972 KB Output is correct
32 Correct 559 ms 10348 KB Output is correct
33 Correct 709 ms 11500 KB Output is correct
34 Correct 547 ms 144748 KB Output is correct
35 Correct 1395 ms 80324 KB Output is correct
36 Correct 2744 ms 148812 KB Output is correct
37 Correct 2241 ms 148968 KB Output is correct
38 Correct 2218 ms 148340 KB Output is correct
39 Correct 1851 ms 116972 KB Output is correct
40 Correct 1 ms 364 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 2 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 577 ms 8684 KB Output is correct
13 Correct 422 ms 9196 KB Output is correct
14 Correct 412 ms 5868 KB Output is correct
15 Correct 468 ms 5612 KB Output is correct
16 Correct 344 ms 4460 KB Output is correct
17 Correct 447 ms 5860 KB Output is correct
18 Correct 414 ms 5228 KB Output is correct
19 Correct 987 ms 10348 KB Output is correct
20 Correct 1409 ms 3948 KB Output is correct
21 Correct 297 ms 1128 KB Output is correct
22 Correct 1676 ms 5116 KB Output is correct
23 Correct 224 ms 9908 KB Output is correct
24 Correct 699 ms 6892 KB Output is correct
25 Correct 1165 ms 10348 KB Output is correct
26 Correct 1051 ms 10348 KB Output is correct
27 Correct 933 ms 9836 KB Output is correct
28 Correct 825 ms 126700 KB Output is correct
29 Correct 2271 ms 151064 KB Output is correct
30 Correct 4513 ms 108908 KB Output is correct
31 Correct 4279 ms 84988 KB Output is correct
32 Correct 560 ms 10332 KB Output is correct
33 Correct 704 ms 11500 KB Output is correct
34 Correct 540 ms 144748 KB Output is correct
35 Correct 1389 ms 80364 KB Output is correct
36 Correct 2780 ms 148800 KB Output is correct
37 Correct 2354 ms 149040 KB Output is correct
38 Correct 2200 ms 148332 KB Output is correct
39 Runtime error 1226 ms 256004 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -