oj.uz

Submission #384173

# Submission time Handle Problem Language Result Execution time Memory
384173 2021-03-31T16:03:29 Z alishahali1382 Game (IOI13_game) C++14
63 / 100
 2013 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=20000000, SEGSZ2=2000000;

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

ll ans;
void Set(Node *v, int tl, int tr, int pos, ll val){
    if (!v) cout<<1/0;
    if (tr-tl==1){
        (v->val)=val;
        return ;
    }
    int mid=(tl+tr)>>1;
    if (pos<mid){
        if (!(v->L)) (v->L)=new Node;
        Set(v->L, tl, mid, pos, val);
    }
    else{
        if (!(v->R)) (v->R)=new Node;
        Set(v->R, mid, tr, pos, val);
    }
    (v->val)=gcd2(((v->L)?v->L->val:0), ((v->R)?v->R->val:0));
    return ;
}
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;
    if (!seg2[id]) seg2[id]=new Node;
    if (tr-tl==1) {
        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);
    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

*/

Compilation message

game.cpp: In function 'void Set(Node*, int, int, int, ll)':
game.cpp:34:20: warning: division by zero [-Wdiv-by-zero]
   34 |     if (!v) cout<<1/0;
      |                   ~^~

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 2 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 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 572 ms 12776 KB Output is correct
5 Correct 419 ms 13164 KB Output is correct
6 Correct 436 ms 9996 KB Output is correct
7 Correct 484 ms 9676 KB Output is correct
8 Correct 322 ms 6764 KB Output is correct
9 Correct 478 ms 9868 KB Output is correct
10 Correct 455 ms 9324 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 2 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 941 ms 15852 KB Output is correct
13 Correct 1374 ms 6304 KB Output is correct
14 Correct 282 ms 1004 KB Output is correct
15 Correct 1631 ms 8776 KB Output is correct
16 Correct 252 ms 18284 KB Output is correct
17 Correct 728 ms 11628 KB Output is correct
18 Correct 1303 ms 18668 KB Output is correct
19 Correct 1103 ms 18924 KB Output is correct
20 Correct 1049 ms 18156 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 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 561 ms 12780 KB Output is correct
13 Correct 402 ms 13068 KB Output is correct
14 Correct 438 ms 10028 KB Output is correct
15 Correct 488 ms 9708 KB Output is correct
16 Correct 324 ms 6764 KB Output is correct
17 Correct 471 ms 9836 KB Output is correct
18 Correct 451 ms 9324 KB Output is correct
19 Correct 939 ms 15952 KB Output is correct
20 Correct 1386 ms 6452 KB Output is correct
21 Correct 282 ms 1132 KB Output is correct
22 Correct 1628 ms 8680 KB Output is correct
23 Correct 244 ms 18284 KB Output is correct
24 Correct 737 ms 11628 KB Output is correct
25 Correct 1320 ms 18628 KB Output is correct
26 Correct 1100 ms 18924 KB Output is correct
27 Correct 1065 ms 18284 KB Output is correct
28 Correct 1121 ms 248864 KB Output is correct
29 Runtime error 2009 ms 256000 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 1 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 564 ms 12768 KB Output is correct
13 Correct 411 ms 13036 KB Output is correct
14 Correct 430 ms 9964 KB Output is correct
15 Correct 470 ms 9708 KB Output is correct
16 Correct 321 ms 6800 KB Output is correct
17 Correct 478 ms 9836 KB Output is correct
18 Correct 442 ms 9324 KB Output is correct
19 Correct 938 ms 16108 KB Output is correct
20 Correct 1375 ms 6636 KB Output is correct
21 Correct 280 ms 1260 KB Output is correct
22 Correct 1614 ms 9068 KB Output is correct
23 Correct 247 ms 18312 KB Output is correct
24 Correct 722 ms 11500 KB Output is correct
25 Correct 1297 ms 18600 KB Output is correct
26 Correct 1114 ms 18916 KB Output is correct
27 Correct 1071 ms 18184 KB Output is correct
28 Correct 1101 ms 248932 KB Output is correct
29 Runtime error 2013 ms 256000 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -