oj.uz

Submission #290109

# Submission time Handle Problem Language Result Execution time Memory
290109 2020-09-03T12:14:36 Z egekabas Game (IOI13_game) C++14
63 / 100
 2092 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);
    }
};
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;
        if(tl == xidx && tr == xidx){
            val->upd(yidx, nv);
            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 xval = 0, yval = 0;
        if(l)
            xval = l->val->get(yidx, yidx);
        if(r)
            yval = r->val->get(yidx, yidx);
        nv = gcd2(xval, yval);
        val->upd(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) {
    
    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 0 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 256 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 1 ms 256 KB Output is correct
4 Correct 730 ms 21448 KB Output is correct
5 Correct 470 ms 21240 KB Output is correct
6 Correct 646 ms 18808 KB Output is correct
7 Correct 741 ms 18552 KB Output is correct
8 Correct 450 ms 13304 KB Output is correct
9 Correct 722 ms 18808 KB Output is correct
10 Correct 707 ms 18296 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 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 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 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 1064 ms 25828 KB Output is correct
13 Correct 1564 ms 12896 KB Output is correct
14 Correct 334 ms 6008 KB Output is correct
15 Correct 1855 ms 17176 KB Output is correct
16 Correct 334 ms 31108 KB Output is correct
17 Correct 1164 ms 21400 KB Output is correct
18 Correct 2092 ms 32748 KB Output is correct
19 Correct 1805 ms 32888 KB Output is correct
20 Correct 1715 ms 32228 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 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 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 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 707 ms 21336 KB Output is correct
13 Correct 459 ms 21344 KB Output is correct
14 Correct 639 ms 18936 KB Output is correct
15 Correct 758 ms 18552 KB Output is correct
16 Correct 457 ms 13304 KB Output is correct
17 Correct 722 ms 18808 KB Output is correct
18 Correct 697 ms 18300 KB Output is correct
19 Correct 1081 ms 25720 KB Output is correct
20 Correct 1548 ms 12744 KB Output is correct
21 Correct 338 ms 5752 KB Output is correct
22 Correct 1817 ms 17144 KB Output is correct
23 Correct 296 ms 31100 KB Output is correct
24 Correct 1141 ms 21376 KB Output is correct
25 Correct 2058 ms 32632 KB Output is correct
26 Correct 1790 ms 32856 KB Output is correct
27 Correct 1794 ms 32400 KB Output is correct
28 Runtime error 832 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 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 368 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 0 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 731 ms 21196 KB Output is correct
13 Correct 468 ms 21240 KB Output is correct
14 Correct 636 ms 18792 KB Output is correct
15 Correct 749 ms 18764 KB Output is correct
16 Correct 451 ms 13336 KB Output is correct
17 Correct 721 ms 18844 KB Output is correct
18 Correct 713 ms 18376 KB Output is correct
19 Correct 1079 ms 25896 KB Output is correct
20 Correct 1583 ms 12736 KB Output is correct
21 Correct 341 ms 5772 KB Output is correct
22 Correct 1828 ms 17144 KB Output is correct
23 Correct 302 ms 31224 KB Output is correct
24 Correct 1175 ms 21352 KB Output is correct
25 Correct 2045 ms 32888 KB Output is correct
26 Correct 1762 ms 32904 KB Output is correct
27 Correct 1745 ms 32080 KB Output is correct
28 Runtime error 820 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -