oj.uz

Submission #290057

# Submission time Handle Problem Language Result Execution time Memory
290057 2020-09-03T10:52:27 Z egekabas Game (IOI13_game) C++14
63 / 100
 2468 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{
    int tl, tr;
    ll 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);
    }
};
struct seg{
    int 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 0 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 759 ms 28576 KB Output is correct
5 Correct 485 ms 28792 KB Output is correct
6 Correct 695 ms 25976 KB Output is correct
7 Correct 812 ms 25660 KB Output is correct
8 Correct 480 ms 15360 KB Output is correct
9 Correct 779 ms 25892 KB Output is correct
10 Correct 769 ms 25336 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 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 2 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 1214 ms 75200 KB Output is correct
13 Correct 1714 ms 42872 KB Output is correct
14 Correct 373 ms 6648 KB Output is correct
15 Correct 1985 ms 57244 KB Output is correct
16 Correct 433 ms 97144 KB Output is correct
17 Correct 1411 ms 54140 KB Output is correct
18 Correct 2468 ms 98780 KB Output is correct
19 Correct 2120 ms 98936 KB Output is correct
20 Correct 2015 ms 98036 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 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 754 ms 28528 KB Output is correct
13 Correct 488 ms 28920 KB Output is correct
14 Correct 736 ms 25924 KB Output is correct
15 Correct 812 ms 25584 KB Output is correct
16 Correct 494 ms 15352 KB Output is correct
17 Correct 761 ms 25776 KB Output is correct
18 Correct 756 ms 25592 KB Output is correct
19 Correct 1217 ms 75128 KB Output is correct
20 Correct 1663 ms 42944 KB Output is correct
21 Correct 375 ms 6776 KB Output is correct
22 Correct 2027 ms 57112 KB Output is correct
23 Correct 441 ms 97144 KB Output is correct
24 Correct 1411 ms 54288 KB Output is correct
25 Correct 2459 ms 98680 KB Output is correct
26 Correct 2106 ms 99016 KB Output is correct
27 Correct 2105 ms 98092 KB Output is correct
28 Runtime error 527 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 0 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 0 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 754 ms 28664 KB Output is correct
13 Correct 501 ms 29076 KB Output is correct
14 Correct 694 ms 26272 KB Output is correct
15 Correct 788 ms 25904 KB Output is correct
16 Correct 477 ms 15736 KB Output is correct
17 Correct 782 ms 25976 KB Output is correct
18 Correct 757 ms 25536 KB Output is correct
19 Correct 1210 ms 74924 KB Output is correct
20 Correct 1692 ms 42872 KB Output is correct
21 Correct 353 ms 6648 KB Output is correct
22 Correct 1975 ms 57464 KB Output is correct
23 Correct 432 ms 97016 KB Output is correct
24 Correct 1376 ms 54520 KB Output is correct
25 Correct 2457 ms 98680 KB Output is correct
26 Correct 2101 ms 98680 KB Output is correct
27 Correct 2063 ms 98156 KB Output is correct
28 Runtime error 491 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -