oj.uz

Submission #384163

# Submission time Handle Problem Language Result Execution time Memory
384163 2021-03-31T15:37:11 Z alishahali1382 Game (IOI13_game) C++14
63 / 100
 2001 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;

struct Node{
    ll val=0;
    Node *L=NULL, *R=NULL;
};

ll ans;
Node* Set(Node *v, int tl, int tr, int pos, ll val){
    // debug2(tl, tr)
    // debug(v)
    if (!v){
        // debug("shit")
        // new Node;
        v=new Node;
    }
    // debug("built new node")
    if (tr-tl==1){
        // debug("shit")
        (v->val)=val;
        // debug("did shit")
        return v;
    }
    // debug("going down")
    int mid=(tl+tr)>>1;
    if (pos<mid) (v->L)=Set((v->L), tl, mid, pos, val);
    else (v->R)=Set((v->R), mid, tr, pos, val);
    // debug("update?")
    (v->val)=gcd2(((v->L)?v->L->val:0), ((v->R)?v->R->val:0));
    // debug("updated")
    return v;
}
void Get(Node *v, int tl, int tr, int l, int r, ll &ans){
    if (r<=tl || tr<=l || !v) return ;
    if (l<=tl && tr<=r){
        ans=gcd2(ans, v->val); // overall log(10^18) for single query of problem
        return ;
    }
    int mid=(tl+tr)>>1;
    Get(v->L, tl, mid, l, r, ans);
    Get(v->R, mid, tr, l, r, ans);
}

int n, m, root;
int L2[SEGSZ2], R2[SEGSZ2], ts2;
Node *seg2[SEGSZ2];
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) {
        // debug("Set")
        seg2[id]=Set(seg2[id], 0, m, y, val);
        // debug("Seted")
        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){
    // debug("update")
    root=Set2(root, 0, n, P, Q, K);
    // debug("done")
}

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 492 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 1 ms 492 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 492 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 568 ms 12652 KB Output is correct
5 Correct 412 ms 13164 KB Output is correct
6 Correct 418 ms 10092 KB Output is correct
7 Correct 489 ms 9708 KB Output is correct
8 Correct 327 ms 6764 KB Output is correct
9 Correct 467 ms 9836 KB Output is correct
10 Correct 438 ms 9452 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 492 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 1 ms 492 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 492 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 965 ms 15852 KB Output is correct
13 Correct 1393 ms 6372 KB Output is correct
14 Correct 285 ms 1004 KB Output is correct
15 Correct 1624 ms 9056 KB Output is correct
16 Correct 252 ms 18228 KB Output is correct
17 Correct 694 ms 11500 KB Output is correct
18 Correct 1263 ms 18708 KB Output is correct
19 Correct 1048 ms 18668 KB Output is correct
20 Correct 1049 ms 18292 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 2 ms 492 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 492 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 492 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 12788 KB Output is correct
13 Correct 419 ms 13036 KB Output is correct
14 Correct 432 ms 9860 KB Output is correct
15 Correct 482 ms 9836 KB Output is correct
16 Correct 328 ms 6700 KB Output is correct
17 Correct 489 ms 9836 KB Output is correct
18 Correct 467 ms 9324 KB Output is correct
19 Correct 946 ms 15896 KB Output is correct
20 Correct 1382 ms 6380 KB Output is correct
21 Correct 284 ms 1004 KB Output is correct
22 Correct 1631 ms 8884 KB Output is correct
23 Correct 245 ms 18284 KB Output is correct
24 Correct 735 ms 11500 KB Output is correct
25 Correct 1299 ms 18540 KB Output is correct
26 Correct 1143 ms 18796 KB Output is correct
27 Correct 1028 ms 18064 KB Output is correct
28 Correct 1056 ms 248940 KB Output is correct
29 Runtime error 2001 ms 256004 KB Execution killed with signal 9
30 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 1 ms 492 KB Output is correct
3 Correct 2 ms 488 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 492 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 492 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 12780 KB Output is correct
13 Correct 420 ms 13036 KB Output is correct
14 Correct 420 ms 9836 KB Output is correct
15 Correct 499 ms 9772 KB Output is correct
16 Correct 340 ms 6764 KB Output is correct
17 Correct 460 ms 9820 KB Output is correct
18 Correct 456 ms 9376 KB Output is correct
19 Correct 952 ms 15968 KB Output is correct
20 Correct 1413 ms 6352 KB Output is correct
21 Correct 287 ms 1004 KB Output is correct
22 Correct 1634 ms 8984 KB Output is correct
23 Correct 253 ms 18284 KB Output is correct
24 Correct 726 ms 11592 KB Output is correct
25 Correct 1308 ms 18796 KB Output is correct
26 Correct 1109 ms 18924 KB Output is correct
27 Correct 1052 ms 18284 KB Output is correct
28 Correct 1049 ms 249196 KB Output is correct
29 Runtime error 1960 ms 256004 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -