oj.uz

Submission #290605

# Submission time Handle Problem Language Result Execution time Memory
290605 2020-09-04T06:54:36 Z egekabas Game (IOI13_game) C++14
63 / 100
 2496 ms 256004 KB 
#include "game.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<ll, ll> pii;
typedef pair<ld, ld> pld;
long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}
int r, c;
    
struct node{
    ll val = 0;
    node *l = nullptr, *r = nullptr;
};
void upd1(node *root, int idx, ll nv, int tl, int tr){
    if(tl == idx && tr == idx){
        root->val = nv;
        return;
    }
    int tm = (tl+tr)/2;
    if(idx <= tm){
        if(!root->l)
            root->l = new node();
        upd1(root->l, idx, nv, tl, tm);
    }
    else{
        if(!root->r)
            root->r = new node();
        upd1(root->r, idx, nv, tm+1, tr);
    }
    ll xval = 0, yval = 0;
    if(root->l)
        xval =  root->l->val;
    if(root->r)
        yval = root->r->val;
    root->val = gcd2(xval, yval);        
}
ll get1(node *root, int lef, int rig, int tl, int tr){
    if(tr < lef || rig < tl)
        return 0;
    if(lef <= tl && tr <= rig){
        return root->val;
    }
    ll xval = 0, yval = 0;
    int tm = (tl+tr)/2;
    if(root->l)
        xval = get1(root->l, lef, rig, tl, tm);
    if(root->r)
        yval = get1(root->r, lef, rig, tm+1, tr);
    return gcd2(xval, yval);
}
struct seg{
    node *val;
    seg *l = nullptr, *r = nullptr;
    seg(){
        val = new node();
    }
};
void upd2(seg *root, int xidx, int yidx, ll nv, int tl, int tr){    
    if(xidx < tl || xidx > tr) return;
    if(tl == xidx && tr == xidx){
        upd1(root->val, yidx, nv, 0, c-1);
        return;
    }
    int tm = (tl+tr)/2;
    if(xidx <= tm){
        if(!root->l)
            root->l = new seg();
        upd2(root->l, xidx, yidx, nv, tl, tm);
    }
    else{
        if(!root->r)
            root->r = new seg();
        upd2(root->r, xidx, yidx, nv, tm+1, tr);
    }
    ll xval = 0, yval = 0;
    if(root->l)
        xval = get1(root->l->val, yidx, yidx, 0, c-1);
    if(root->r)
        yval = get1(root->r->val, yidx, yidx, 0, c-1);
    nv = gcd2(xval, yval);
    upd1(root->val, yidx, nv, 0, c-1);
}
ll get2(seg *root, int xl, int xr, int yl, int yr, int tl, int tr){
    if(tr < xl || xr < tl)
        return 0;
    if(xl <= tl && tr <= xr){
        return get1(root->val, yl, yr, 0, c-1);
    }
    ll xval = 0, yval = 0;
    int tm = (tl+tr)/2;
    if(root->l)
        xval = get2(root->l, xl, xr, yl, yr, tl, tm);
    if(root->r)
        yval = get2(root->r, xl, xr, yl, yr, tm+1, tr);
    return gcd2(xval, yval);
}
seg *root;
void init(int R, int C) {
    r = R;
    c = C;
    root = new seg();
}
    
void update(int P, int Q, long long K) {
    upd2(root,P, Q, K, 0, r-1);
}
    
long long calculate(int P, int Q, int U, int V){    
    return get2(root, P, U, Q, V, 0, r-1);
}

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 689 ms 13304 KB Output is correct
5 Correct 756 ms 13632 KB Output is correct
6 Correct 622 ms 10620 KB Output is correct
7 Correct 715 ms 10488 KB Output is correct
8 Correct 471 ms 7672 KB Output is correct
9 Correct 664 ms 10640 KB Output is correct
10 Correct 674 ms 10172 KB Output is correct
11 Correct 1 ms 256 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1038 ms 17320 KB Output is correct
13 Correct 1687 ms 7768 KB Output is correct
14 Correct 364 ms 2464 KB Output is correct
15 Correct 1974 ms 10268 KB Output is correct
16 Correct 300 ms 20184 KB Output is correct
17 Correct 995 ms 13304 KB Output is correct
18 Correct 1890 ms 20380 KB Output is correct
19 Correct 1561 ms 20520 KB Output is correct
20 Correct 1439 ms 20024 KB Output is correct
21 Correct 0 ms 256 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 416 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 688 ms 14284 KB Output is correct
13 Correct 499 ms 14712 KB Output is correct
14 Correct 565 ms 11548 KB Output is correct
15 Correct 649 ms 11256 KB Output is correct
16 Correct 425 ms 8440 KB Output is correct
17 Correct 711 ms 11448 KB Output is correct
18 Correct 627 ms 10872 KB Output is correct
19 Correct 1008 ms 17464 KB Output is correct
20 Correct 1567 ms 7780 KB Output is correct
21 Correct 331 ms 2608 KB Output is correct
22 Correct 1869 ms 10448 KB Output is correct
23 Correct 273 ms 19964 KB Output is correct
24 Correct 1042 ms 13132 KB Output is correct
25 Correct 1783 ms 20244 KB Output is correct
26 Correct 1613 ms 20272 KB Output is correct
27 Correct 1539 ms 19496 KB Output is correct
28 Correct 1300 ms 252324 KB Output is correct
29 Runtime error 2496 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 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 648 ms 14072 KB Output is correct
13 Correct 522 ms 14456 KB Output is correct
14 Correct 728 ms 11256 KB Output is correct
15 Correct 756 ms 11060 KB Output is correct
16 Correct 449 ms 8088 KB Output is correct
17 Correct 650 ms 11228 KB Output is correct
18 Correct 632 ms 10708 KB Output is correct
19 Correct 1139 ms 17272 KB Output is correct
20 Correct 1583 ms 7712 KB Output is correct
21 Correct 461 ms 2424 KB Output is correct
22 Correct 1911 ms 9892 KB Output is correct
23 Correct 288 ms 19520 KB Output is correct
24 Correct 1028 ms 12480 KB Output is correct
25 Correct 1786 ms 19140 KB Output is correct
26 Correct 1476 ms 18980 KB Output is correct
27 Correct 1445 ms 18160 KB Output is correct
28 Correct 1250 ms 251652 KB Output is correct
29 Runtime error 2388 ms 256004 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -