oj.uz

Submission #290065

# Submission time Handle Problem Language Result Execution time Memory
290065 2020-09-03T11:01:59 Z egekabas Game (IOI13_game) C++14
63 / 100
 2184 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 = tr = -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);
    }
};
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(ll xidx, ll yidx, ll nv){    
        if(xidx < tl || xidx > tr) return;
        val->upd(yidx, mpp[yidx].get(tl, tr));
        if(tl == tr){
            return;
        }
        ll 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 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 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 728 ms 19192 KB Output is correct
5 Correct 464 ms 19496 KB Output is correct
6 Correct 647 ms 16496 KB Output is correct
7 Correct 788 ms 16312 KB Output is correct
8 Correct 467 ms 10400 KB Output is correct
9 Correct 779 ms 16376 KB Output is correct
10 Correct 759 ms 15932 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 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 1084 ms 25336 KB Output is correct
13 Correct 1557 ms 11180 KB Output is correct
14 Correct 335 ms 1144 KB Output is correct
15 Correct 1808 ms 15412 KB Output is correct
16 Correct 278 ms 31540 KB Output is correct
17 Correct 1179 ms 18980 KB Output is correct
18 Correct 2082 ms 31992 KB Output is correct
19 Correct 1760 ms 32248 KB Output is correct
20 Correct 1696 ms 31356 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 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 708 ms 19328 KB Output is correct
13 Correct 467 ms 19484 KB Output is correct
14 Correct 639 ms 16564 KB Output is correct
15 Correct 767 ms 16376 KB Output is correct
16 Correct 456 ms 10184 KB Output is correct
17 Correct 724 ms 16504 KB Output is correct
18 Correct 725 ms 15992 KB Output is correct
19 Correct 1051 ms 25464 KB Output is correct
20 Correct 1568 ms 10872 KB Output is correct
21 Correct 334 ms 1148 KB Output is correct
22 Correct 1814 ms 15416 KB Output is correct
23 Correct 278 ms 31480 KB Output is correct
24 Correct 1177 ms 19044 KB Output is correct
25 Correct 2086 ms 32016 KB Output is correct
26 Correct 1781 ms 32332 KB Output is correct
27 Correct 1706 ms 31356 KB Output is correct
28 Runtime error 738 ms 256000 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 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 0 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 730 ms 19236 KB Output is correct
13 Correct 456 ms 19704 KB Output is correct
14 Correct 651 ms 16504 KB Output is correct
15 Correct 746 ms 16276 KB Output is correct
16 Correct 460 ms 10292 KB Output is correct
17 Correct 725 ms 16376 KB Output is correct
18 Correct 699 ms 15864 KB Output is correct
19 Correct 1049 ms 25336 KB Output is correct
20 Correct 1557 ms 11000 KB Output is correct
21 Correct 328 ms 1264 KB Output is correct
22 Correct 1825 ms 15292 KB Output is correct
23 Correct 281 ms 31480 KB Output is correct
24 Correct 1179 ms 19132 KB Output is correct
25 Correct 2184 ms 31964 KB Output is correct
26 Correct 1812 ms 32040 KB Output is correct
27 Correct 1746 ms 31428 KB Output is correct
28 Runtime error 758 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -