oj.uz

Submission #290150

# Submission time Handle Problem Language Result Execution time Memory
290150 2020-09-03T12:39:49 Z egekabas Game (IOI13_game) C++14
63 / 100
 2474 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{
    ll val = 0;
    node *l = nullptr, *r = nullptr;
    
    void upd(int idx, ll nv, int tl, int tr){
        if(tl == idx && tr == idx){
            val = nv;
            return;
        }
        int tm = (tl+tr)/2;
        if(idx <= tm){
            if(!l)
                l = new node();
            l->upd(idx, nv, tl, tm);
        }
        else{
            if(!r)
                r = new node();
            r->upd(idx, nv, tm+1, tr);
        }
        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, int tl, int tr){
        if(tr < lef || rig < tl)
            return 0;
        if(lef <= tl && tr <= rig){
            return val;
        }
        ll xval = 0, yval = 0;
        int tm = (tl+tr)/2;
        if(l)
            xval = l->get(lef, rig, tl, tm);
        if(r)
            yval = r->get(lef, rig, tm+1, tr);
        return gcd2(xval, yval);
    }
};
struct seg{
    node *val;
    seg *l = nullptr, *r = nullptr;
    seg(){
        val = new node();
    }
    void upd(int xidx, int yidx, ll nv, int tl, int tr){    
        if(xidx < tl || xidx > tr) return;
        if(tl == xidx && tr == xidx){
            val->upd(yidx, nv, 0, c-1);
            return;
        }
        int tm = (tl+tr)/2;
        if(xidx <= tm){
            if(!l)
                l = new seg();
            l->upd(xidx, yidx, nv, tl, tm);
        }
        else{
            if(!r)
                r = new seg();
            r->upd(xidx, yidx, nv, tm+1, tr);
        }
        ll xval = 0, yval = 0;
        if(l)
            xval = l->val->get(yidx, yidx, 0, c-1);
        if(r)
            yval = r->val->get(yidx, yidx, 0, c-1);
        nv = gcd2(xval, yval);
        val->upd(yidx, nv, 0, c-1);
    }
    ll get(int xl, int xr, int yl, int yr, int tl, int tr){
        if(tr < xl || xr < tl)
            return 0;
        if(xl <= tl && tr <= xr){
            return val->get(yl, yr, 0, c-1);
        }
        ll xval = 0, yval = 0;
        int tm = (tl+tr)/2;
        if(l)
            xval = l->get(xl, xr, yl, yr, tl, tm);
        if(r)
            yval = r->get(xl, xr, yl, yr, tm+1, tr);
        return gcd2(xval, yval);
    }
};
seg root;
void init(int R, int C) {
    r = rr = R;
    c = C;
    root =  seg();
}
    
void update(int P, int Q, long long K) {
    root.upd(P, Q, K, 0, r-1);
}
    
long long calculate(int P, int Q, int U, int V){    
    return root.get(P, U, Q, V, 0, r-1);
}

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 384 KB Output is correct
3 Correct 1 ms 384 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 384 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 1 ms 384 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 634 ms 13436 KB Output is correct
5 Correct 482 ms 13916 KB Output is correct
6 Correct 604 ms 10424 KB Output is correct
7 Correct 635 ms 9976 KB Output is correct
8 Correct 485 ms 7160 KB Output is correct
9 Correct 629 ms 10148 KB Output is correct
10 Correct 656 ms 9740 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 384 KB Output is correct
3 Correct 1 ms 384 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 384 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 288 KB Output is correct
12 Correct 963 ms 16068 KB Output is correct
13 Correct 1519 ms 6184 KB Output is correct
14 Correct 358 ms 992 KB Output is correct
15 Correct 1769 ms 8824 KB Output is correct
16 Correct 281 ms 18296 KB Output is correct
17 Correct 1000 ms 11532 KB Output is correct
18 Correct 1893 ms 18572 KB Output is correct
19 Correct 1496 ms 18836 KB Output is correct
20 Correct 1369 ms 18164 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 1 ms 384 KB Output is correct
3 Correct 1 ms 384 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 384 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 616 ms 12736 KB Output is correct
13 Correct 432 ms 13048 KB Output is correct
14 Correct 552 ms 9848 KB Output is correct
15 Correct 638 ms 9592 KB Output is correct
16 Correct 425 ms 6740 KB Output is correct
17 Correct 620 ms 9848 KB Output is correct
18 Correct 581 ms 9336 KB Output is correct
19 Correct 968 ms 15864 KB Output is correct
20 Correct 1552 ms 6240 KB Output is correct
21 Correct 323 ms 1144 KB Output is correct
22 Correct 1857 ms 8768 KB Output is correct
23 Correct 294 ms 18296 KB Output is correct
24 Correct 1064 ms 11512 KB Output is correct
25 Correct 2009 ms 18888 KB Output is correct
26 Correct 1627 ms 18800 KB Output is correct
27 Correct 1549 ms 18124 KB Output is correct
28 Correct 1271 ms 251728 KB Output is correct
29 Runtime error 2474 ms 256004 KB Execution killed with signal 9
30 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 384 KB Output is correct
3 Correct 1 ms 384 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 384 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 651 ms 12664 KB Output is correct
13 Correct 434 ms 12976 KB Output is correct
14 Correct 594 ms 9848 KB Output is correct
15 Correct 658 ms 9676 KB Output is correct
16 Correct 441 ms 6648 KB Output is correct
17 Correct 769 ms 10000 KB Output is correct
18 Correct 651 ms 9336 KB Output is correct
19 Correct 983 ms 15864 KB Output is correct
20 Correct 1485 ms 6228 KB Output is correct
21 Correct 329 ms 1016 KB Output is correct
22 Correct 1745 ms 8720 KB Output is correct
23 Correct 277 ms 18296 KB Output is correct
24 Correct 986 ms 11564 KB Output is correct
25 Correct 1768 ms 18700 KB Output is correct
26 Correct 1494 ms 18808 KB Output is correct
27 Correct 1502 ms 18204 KB Output is correct
28 Correct 1244 ms 251640 KB Output is correct
29 Runtime error 2216 ms 256000 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -