oj.uz

Submission #290056

# Submission time Handle Problem Language Result Execution time Memory
290056 2020-09-03T10:48:51 Z egekabas Game (IOI13_game) C++14
63 / 100
 2538 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;
}
ll r, c, rr;

struct node{
    ll tl, tr, val;
    node *l = nullptr, *r = nullptr;
    node(ll tlval, ll trval){
        tl = tlval;
        tr = trval;
        val = 0;
    }
    node(){
        tl = 0;
        tr = rr-1;
        val = 0;
    }   
    void upd(ll idx, ll nv){
        if(tl == idx && tr == idx){
            val = nv;
            return;
        }
        ll 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(ll lef, ll 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);
    }
};
ll cnt;
struct seg{
    ll tl, tr;
    node *val;
    seg *l = nullptr, *r = nullptr;
    map<int, node> v;
    seg(ll tval, ll rval){
        tl = tval;
        tr = rval;
        val = new node(0, c-1);
    }
    seg(){}
    void upd(ll xidx, ll yidx, ll nv){    
        if(xidx < tl || xidx > tr) return;
        v[yidx].upd(xidx, nv);
        val->upd(yidx, v[yidx].val);
        if(tl == tr){
            return;
        }
        ll tm = (tl+tr)/2;
        if(!l)
            l = new seg(tl, tm);
        l->upd(xidx, yidx, nv);
        if(!r)
            r = new seg(tm+1, tr);
        r->upd(xidx, yidx, nv);
    }
    ll get(ll xl, ll xr, ll yl, ll 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 1 ms 256 KB Output is correct
2 Correct 2 ms 768 KB Output is correct
3 Correct 2 ms 768 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 768 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 768 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 512 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 384 KB Output is correct
4 Correct 756 ms 28156 KB Output is correct
5 Correct 500 ms 28408 KB Output is correct
6 Correct 712 ms 25592 KB Output is correct
7 Correct 818 ms 25356 KB Output is correct
8 Correct 493 ms 14620 KB Output is correct
9 Correct 801 ms 25464 KB Output is correct
10 Correct 761 ms 25080 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 0 ms 256 KB Output is correct
2 Correct 2 ms 768 KB Output is correct
3 Correct 2 ms 768 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 768 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 768 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 1229 ms 77324 KB Output is correct
13 Correct 1693 ms 43688 KB Output is correct
14 Correct 373 ms 6904 KB Output is correct
15 Correct 1981 ms 58088 KB Output is correct
16 Correct 426 ms 98624 KB Output is correct
17 Correct 1369 ms 55032 KB Output is correct
18 Correct 2456 ms 100472 KB Output is correct
19 Correct 2149 ms 100296 KB Output is correct
20 Correct 2067 ms 99984 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 768 KB Output is correct
3 Correct 2 ms 768 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 2 ms 768 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 768 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 757 ms 28024 KB Output is correct
13 Correct 505 ms 28412 KB Output is correct
14 Correct 711 ms 25768 KB Output is correct
15 Correct 807 ms 25468 KB Output is correct
16 Correct 498 ms 14840 KB Output is correct
17 Correct 817 ms 25656 KB Output is correct
18 Correct 755 ms 25080 KB Output is correct
19 Correct 1244 ms 77560 KB Output is correct
20 Correct 1710 ms 43640 KB Output is correct
21 Correct 369 ms 6648 KB Output is correct
22 Correct 2009 ms 58040 KB Output is correct
23 Correct 431 ms 98696 KB Output is correct
24 Correct 1439 ms 54904 KB Output is correct
25 Correct 2484 ms 100276 KB Output is correct
26 Correct 2142 ms 100372 KB Output is correct
27 Correct 2045 ms 99764 KB Output is correct
28 Runtime error 537 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 2 ms 768 KB Output is correct
3 Correct 2 ms 768 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 768 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 768 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 750 ms 28408 KB Output is correct
13 Correct 494 ms 28792 KB Output is correct
14 Correct 719 ms 25976 KB Output is correct
15 Correct 819 ms 25720 KB Output is correct
16 Correct 480 ms 15096 KB Output is correct
17 Correct 799 ms 25848 KB Output is correct
18 Correct 767 ms 25468 KB Output is correct
19 Correct 1237 ms 77268 KB Output is correct
20 Correct 1702 ms 43648 KB Output is correct
21 Correct 367 ms 6776 KB Output is correct
22 Correct 2001 ms 58320 KB Output is correct
23 Correct 434 ms 98680 KB Output is correct
24 Correct 1419 ms 54792 KB Output is correct
25 Correct 2538 ms 100276 KB Output is correct
26 Correct 2192 ms 100488 KB Output is correct
27 Correct 2107 ms 99708 KB Output is correct
28 Runtime error 493 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -