oj.uz

Submission #290071

# Submission time Handle Problem Language Result Execution time Memory
290071 2020-09-03T11:11:50 Z egekabas Game (IOI13_game) C++14
63 / 100
 2070 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, rr;

struct node{
    int tl, tr;
    ll val;
    node *l = nullptr, *r = nullptr;
    node(int tlval, int trval){
        tl = tlval;
        tr = trval;
        val = 0;
    }
    node(){
        tl = tr = -1;
        val = 0;
    }
    void upd(int idx, ll nv){
        if(tl == idx && tr == idx){
            val = nv;
            return;
        }
        int tm = (tl+tr)/2;
        if(idx <= tm){
            if(!l)
                l = new node(tl, tm);
            l->upd(idx, nv);
        }
        else{
            if(!r)
                r = new node(tm+1, tr);
            r->upd(idx, nv);
        }
        ll xval = 0, yval = 0;
        if(l)
            xval =  l->val;
        if(r)
            yval = r->val;
        val = gcd2(xval, yval);        
    }
    ll get(int lef, int rig){
        
        if(tr < lef || rig < tl)
            return 0;
        if(lef <= tl && tr <= rig){
            return val;
        }
        ll xval = 0, yval = 0;
        if(l)
            xval = l->get(lef, rig);
        if(r)
            yval = r->get(lef, rig);
        return gcd2(xval, yval);
    }
};
unordered_map<int, node> mpp;
struct seg{
    int tl, tr;
    node *val;
    seg *l = nullptr, *r = nullptr;
    seg(ll tval, ll rval){
        tl = tval;
        tr = rval;
        val = new node(0, c-1);
    }
    seg(){}
    void upd(int xidx, int yidx, ll nv){    
        if(xidx < tl || xidx > tr) return;
        val->upd(yidx, mpp[yidx].get(tl, tr));
        if(tl == tr){
            return;
        }
        int tm = (tl+tr)/2;
        if(xidx <= tm){
            if(!l)
                l = new seg(tl, tm);
            l->upd(xidx, yidx, nv);
        }
        else{
            if(!r)
                r = new seg(tm+1, tr);
            r->upd(xidx, yidx, nv);
        }
    }
    ll get(int xl, int xr, int yl, int yr){
        if(tr < xl || xr < tl)
            return 0;
        if(xl <= tl && tr <= xr){
            return val->get(yl, yr);
        }
        ll xval = 0, yval = 0;
        if(l)
            xval = l->get(xl, xr, yl, yr);
        if(r)
            yval = r->get(xl, xr, yl, yr);
        return gcd2(xval, yval);
    }
};
seg root;
void init(int R, int C) {
    r = rr = R;
    c = C;
    root = seg(0, r-1);
}
    
void update(int P, int Q, long long K) {
    if(mpp[Q].tl == -1)
        mpp[Q] = node(0, r-1);
    mpp[Q].upd(P, K);
    root.upd(P, Q, K);
}
    
long long calculate(int P, int Q, int U, int V){    
    return root.get(P, U, Q, V);
}

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   18 |  int res;
      |      ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 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 512 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 512 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 1 ms 256 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 693 ms 19612 KB Output is correct
5 Correct 453 ms 19704 KB Output is correct
6 Correct 631 ms 16760 KB Output is correct
7 Correct 765 ms 16764 KB Output is correct
8 Correct 449 ms 10488 KB Output is correct
9 Correct 693 ms 16664 KB Output is correct
10 Correct 714 ms 16232 KB Output is correct
11 Correct 0 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 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1058 ms 25508 KB Output is correct
13 Correct 1559 ms 11000 KB Output is correct
14 Correct 315 ms 1400 KB Output is correct
15 Correct 1823 ms 15576 KB Output is correct
16 Correct 264 ms 31736 KB Output is correct
17 Correct 1138 ms 19320 KB Output is correct
18 Correct 2019 ms 32120 KB Output is correct
19 Correct 1748 ms 32292 KB Output is correct
20 Correct 1691 ms 31612 KB Output is correct
21 Correct 1 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 512 KB Output is correct
3 Correct 1 ms 512 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 512 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 512 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 699 ms 19452 KB Output is correct
13 Correct 449 ms 19704 KB Output is correct
14 Correct 634 ms 16760 KB Output is correct
15 Correct 742 ms 16504 KB Output is correct
16 Correct 443 ms 10600 KB Output is correct
17 Correct 711 ms 16888 KB Output is correct
18 Correct 688 ms 16304 KB Output is correct
19 Correct 1063 ms 25704 KB Output is correct
20 Correct 1540 ms 11180 KB Output is correct
21 Correct 322 ms 1400 KB Output is correct
22 Correct 1809 ms 15480 KB Output is correct
23 Correct 274 ms 31736 KB Output is correct
24 Correct 1187 ms 19192 KB Output is correct
25 Correct 2064 ms 32516 KB Output is correct
26 Correct 1690 ms 32376 KB Output is correct
27 Correct 1637 ms 31484 KB Output is correct
28 Runtime error 761 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 693 ms 20184 KB Output is correct
13 Correct 451 ms 20524 KB Output is correct
14 Correct 631 ms 17656 KB Output is correct
15 Correct 762 ms 17472 KB Output is correct
16 Correct 446 ms 11000 KB Output is correct
17 Correct 720 ms 17528 KB Output is correct
18 Correct 686 ms 17040 KB Output is correct
19 Correct 1045 ms 26636 KB Output is correct
20 Correct 1519 ms 11640 KB Output is correct
21 Correct 331 ms 1784 KB Output is correct
22 Correct 1817 ms 15992 KB Output is correct
23 Correct 271 ms 32248 KB Output is correct
24 Correct 1129 ms 19624 KB Output is correct
25 Correct 2070 ms 32640 KB Output is correct
26 Correct 1714 ms 32820 KB Output is correct
27 Correct 1672 ms 32120 KB Output is correct
28 Runtime error 743 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -