oj.uz

Submission #290058

# Submission time Handle Problem Language Result Execution time Memory
290058 2020-09-03T10:53:55 Z egekabas Game (IOI13_game) C++14
63 / 100
 2504 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(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) {
    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 1 ms 288 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 0 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 784 ms 28664 KB Output is correct
5 Correct 488 ms 28792 KB Output is correct
6 Correct 704 ms 26384 KB Output is correct
7 Correct 813 ms 25848 KB Output is correct
8 Correct 488 ms 15608 KB Output is correct
9 Correct 791 ms 25976 KB Output is correct
10 Correct 750 ms 25464 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 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 1243 ms 75000 KB Output is correct
13 Correct 1662 ms 39416 KB Output is correct
14 Correct 342 ms 2552 KB Output is correct
15 Correct 2005 ms 53240 KB Output is correct
16 Correct 441 ms 93432 KB Output is correct
17 Correct 1401 ms 49912 KB Output is correct
18 Correct 2490 ms 94200 KB Output is correct
19 Correct 2138 ms 94132 KB Output is correct
20 Correct 2101 ms 93340 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 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 1 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 793 ms 28664 KB Output is correct
13 Correct 480 ms 28920 KB Output is correct
14 Correct 704 ms 26088 KB Output is correct
15 Correct 881 ms 25848 KB Output is correct
16 Correct 512 ms 15736 KB Output is correct
17 Correct 801 ms 25960 KB Output is correct
18 Correct 795 ms 25748 KB Output is correct
19 Correct 1230 ms 75000 KB Output is correct
20 Correct 1699 ms 39708 KB Output is correct
21 Correct 369 ms 2808 KB Output is correct
22 Correct 2005 ms 53444 KB Output is correct
23 Correct 423 ms 93572 KB Output is correct
24 Correct 1402 ms 49912 KB Output is correct
25 Correct 2504 ms 93988 KB Output is correct
26 Correct 2201 ms 93960 KB Output is correct
27 Correct 2122 ms 93356 KB Output is correct
28 Runtime error 481 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 1 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 767 ms 28408 KB Output is correct
13 Correct 502 ms 28156 KB Output is correct
14 Correct 729 ms 25592 KB Output is correct
15 Correct 869 ms 25336 KB Output is correct
16 Correct 521 ms 15096 KB Output is correct
17 Correct 803 ms 25592 KB Output is correct
18 Correct 801 ms 25208 KB Output is correct
19 Correct 1326 ms 74488 KB Output is correct
20 Correct 1734 ms 39292 KB Output is correct
21 Correct 365 ms 2424 KB Output is correct
22 Correct 2037 ms 52984 KB Output is correct
23 Correct 423 ms 93304 KB Output is correct
24 Correct 1438 ms 49528 KB Output is correct
25 Correct 2495 ms 93688 KB Output is correct
26 Correct 2215 ms 93780 KB Output is correct
27 Correct 2105 ms 93220 KB Output is correct
28 Runtime error 470 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -