oj.uz

Submission #384174

# Submission time Handle Problem Language Result Execution time Memory
384174 2021-03-31T16:08:32 Z alishahali1382 Game (IOI13_game) C++14
80 / 100
 4621 ms 256000 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=19000000, SEGSZ2=700000;
 
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){
        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;
    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);
    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;
}

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 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 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 582 ms 8888 KB Output is correct
5 Correct 415 ms 8940 KB Output is correct
6 Correct 429 ms 5868 KB Output is correct
7 Correct 478 ms 5408 KB Output is correct
8 Correct 332 ms 4372 KB Output is correct
9 Correct 468 ms 5612 KB Output is correct
10 Correct 446 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 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 2 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1004 ms 10284 KB Output is correct
13 Correct 1418 ms 3780 KB Output is correct
14 Correct 297 ms 948 KB Output is correct
15 Correct 1685 ms 5100 KB Output is correct
16 Correct 228 ms 9708 KB Output is correct
17 Correct 683 ms 6764 KB Output is correct
18 Correct 1257 ms 10220 KB Output is correct
19 Correct 1031 ms 10300 KB Output is correct
20 Correct 961 ms 9720 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 578 ms 8684 KB Output is correct
13 Correct 433 ms 8948 KB Output is correct
14 Correct 410 ms 5740 KB Output is correct
15 Correct 480 ms 5500 KB Output is correct
16 Correct 331 ms 4352 KB Output is correct
17 Correct 484 ms 5808 KB Output is correct
18 Correct 432 ms 5228 KB Output is correct
19 Correct 999 ms 10388 KB Output is correct
20 Correct 1415 ms 3720 KB Output is correct
21 Correct 305 ms 1000 KB Output is correct
22 Correct 1706 ms 4972 KB Output is correct
23 Correct 222 ms 9708 KB Output is correct
24 Correct 687 ms 6636 KB Output is correct
25 Correct 1297 ms 9964 KB Output is correct
26 Correct 1036 ms 10304 KB Output is correct
27 Correct 965 ms 9692 KB Output is correct
28 Correct 815 ms 125804 KB Output is correct
29 Correct 2240 ms 140768 KB Output is correct
30 Correct 4621 ms 101964 KB Output is correct
31 Correct 4263 ms 77984 KB Output is correct
32 Correct 565 ms 1132 KB Output is correct
33 Correct 712 ms 2476 KB Output is correct
34 Correct 555 ms 137956 KB Output is correct
35 Correct 1453 ms 70460 KB Output is correct
36 Correct 2762 ms 138100 KB Output is correct
37 Correct 2299 ms 138764 KB Output is correct
38 Correct 2265 ms 137736 KB Output is correct
39 Correct 1906 ms 106468 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 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 2 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 580 ms 8684 KB Output is correct
13 Correct 416 ms 8940 KB Output is correct
14 Correct 416 ms 5740 KB Output is correct
15 Correct 482 ms 5556 KB Output is correct
16 Correct 330 ms 4332 KB Output is correct
17 Correct 457 ms 5740 KB Output is correct
18 Correct 444 ms 5200 KB Output is correct
19 Correct 1000 ms 10216 KB Output is correct
20 Correct 1432 ms 3880 KB Output is correct
21 Correct 296 ms 1004 KB Output is correct
22 Correct 1696 ms 4976 KB Output is correct
23 Correct 231 ms 9708 KB Output is correct
24 Correct 682 ms 6764 KB Output is correct
25 Correct 1244 ms 10220 KB Output is correct
26 Correct 1049 ms 10172 KB Output is correct
27 Correct 979 ms 9752 KB Output is correct
28 Correct 828 ms 125552 KB Output is correct
29 Correct 2272 ms 140920 KB Output is correct
30 Correct 4611 ms 101916 KB Output is correct
31 Correct 4311 ms 78008 KB Output is correct
32 Correct 561 ms 1288 KB Output is correct
33 Correct 723 ms 2600 KB Output is correct
34 Correct 541 ms 138040 KB Output is correct
35 Correct 1484 ms 70780 KB Output is correct
36 Correct 2769 ms 138440 KB Output is correct
37 Correct 2319 ms 138476 KB Output is correct
38 Correct 2255 ms 137836 KB Output is correct
39 Runtime error 1239 ms 256000 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -