oj.uz

Submission #384158

# Submission time Handle Problem Language Result Execution time Memory
384158 2021-03-31T15:11:55 Z alishahali1382 Game (IOI13_game) C++14
63 / 100
 1700 ms 236652 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=7000000, SEGSZ2=300000;

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 384 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 384 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 376 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 384 KB Output is correct
4 Correct 571 ms 13036 KB Output is correct
5 Correct 423 ms 12788 KB Output is correct
6 Correct 427 ms 10368 KB Output is correct
7 Correct 465 ms 10220 KB Output is correct
8 Correct 329 ms 8812 KB Output is correct
9 Correct 455 ms 10220 KB Output is correct
10 Correct 424 ms 9836 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 2 ms 364 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 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 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 984 ms 14460 KB Output is correct
13 Correct 1414 ms 7692 KB Output is correct
14 Correct 294 ms 5740 KB Output is correct
15 Correct 1680 ms 9660 KB Output is correct
16 Correct 221 ms 13932 KB Output is correct
17 Correct 654 ms 11628 KB Output is correct
18 Correct 1174 ms 15444 KB Output is correct
19 Correct 985 ms 15700 KB Output is correct
20 Correct 954 ms 15080 KB Output is correct
21 Correct 1 ms 364 KB Output is correct

Subtask #4
0 / 17.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 579 ms 13036 KB Output is correct
13 Correct 425 ms 13164 KB Output is correct
14 Correct 416 ms 10476 KB Output is correct
15 Correct 465 ms 10092 KB Output is correct
16 Correct 337 ms 8812 KB Output is correct
17 Correct 434 ms 10220 KB Output is correct
18 Correct 415 ms 9836 KB Output is correct
19 Correct 987 ms 14444 KB Output is correct
20 Correct 1412 ms 7916 KB Output is correct
21 Correct 296 ms 5712 KB Output is correct
22 Correct 1673 ms 9620 KB Output is correct
23 Correct 227 ms 14060 KB Output is correct
24 Correct 675 ms 11500 KB Output is correct
25 Correct 1187 ms 15468 KB Output is correct
26 Correct 1022 ms 15596 KB Output is correct
27 Correct 931 ms 15084 KB Output is correct
28 Runtime error 841 ms 236652 KB Execution killed with signal 11
29 Halted 0 ms 0 KB -

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 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 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 571 ms 13036 KB Output is correct
13 Correct 420 ms 12992 KB Output is correct
14 Correct 424 ms 10516 KB Output is correct
15 Correct 481 ms 10092 KB Output is correct
16 Correct 330 ms 8664 KB Output is correct
17 Correct 433 ms 10220 KB Output is correct
18 Correct 419 ms 9836 KB Output is correct
19 Correct 986 ms 14316 KB Output is correct
20 Correct 1410 ms 7916 KB Output is correct
21 Correct 298 ms 5740 KB Output is correct
22 Correct 1700 ms 9500 KB Output is correct
23 Correct 219 ms 13932 KB Output is correct
24 Correct 648 ms 11628 KB Output is correct
25 Correct 1202 ms 15468 KB Output is correct
26 Correct 936 ms 15440 KB Output is correct
27 Correct 967 ms 15084 KB Output is correct
28 Runtime error 832 ms 236448 KB Execution killed with signal 11
29 Halted 0 ms 0 KB -