oj.uz

Submission #290126

# Submission time Handle Problem Language Result Execution time Memory
290126 2020-09-03T12:26:30 Z egekabas Game (IOI13_game) C++14
63 / 100
 2486 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<int, int> 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;
    
struct node{
    int tl, tr;
    ll val;
    node *l = nullptr, *r = nullptr;
    node(int tlval, int trval){
        tl = tlval;
        tr = trval;
        val = 0;
    }
    node(){
    }
    void relax(){
        if(l && l->val == 0){
            delete l;
            l = nullptr;
        }
        if(r && r->val == 0){
            delete r;
            r = nullptr;
        }
    }
    void upd(int idx, ll nv){
        if(tl == idx && tr == idx){
            val = nv;
            return;
        }
        int 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);   
        relax();     
    }
    ll get(int lef, int 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;
    seg(ll tval, ll rval){
        tl = tval;
        tr = rval;
        val = new node(0, c-1);
    }
    seg(){}
    void upd(int xidx, int yidx, ll nv){
        if(xidx < tl || xidx > tr) return;
        if(tl == xidx && tr == xidx){
            val->upd(yidx, nv);
            return;
        }
        int 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 xval = 0, yval = 0;
        if(l)
            xval = l->val->get(yidx, yidx);
        if(r)
            yval = r->val->get(yidx, yidx);
        nv = gcd2(xval, yval);
        val->upd(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 = 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:25:5: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   25 |     while(res != 1);
      |     ^~~~~
grader.c:26:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   26 |  res = fscanf(f, "%d", &C);
      |  ^~~
grader.c:27:5: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   27 |     while(res != 1);
      |     ^~~~~
grader.c:28:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   28 |  res = fscanf(f, "%d", &N);
      |  ^~~

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 2 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 1 ms 256 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 488 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 694 ms 21240 KB Output is correct
5 Correct 466 ms 21112 KB Output is correct
6 Correct 640 ms 18740 KB Output is correct
7 Correct 799 ms 18600 KB Output is correct
8 Correct 456 ms 13304 KB Output is correct
9 Correct 783 ms 18808 KB Output is correct
10 Correct 744 ms 18272 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 512 KB Output is correct
3 Correct 2 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 1 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 1095 ms 25784 KB Output is correct
13 Correct 1530 ms 12796 KB Output is correct
14 Correct 326 ms 5752 KB Output is correct
15 Correct 1798 ms 16976 KB Output is correct
16 Correct 306 ms 31096 KB Output is correct
17 Correct 1184 ms 21496 KB Output is correct
18 Correct 2162 ms 32504 KB Output is correct
19 Correct 1873 ms 32856 KB Output is correct
20 Correct 1714 ms 31992 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 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 1 ms 384 KB Output is correct
8 Correct 1 ms 384 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 21368 KB Output is correct
13 Correct 481 ms 21088 KB Output is correct
14 Correct 648 ms 18932 KB Output is correct
15 Correct 743 ms 18552 KB Output is correct
16 Correct 442 ms 13308 KB Output is correct
17 Correct 733 ms 18680 KB Output is correct
18 Correct 678 ms 18168 KB Output is correct
19 Correct 1072 ms 26104 KB Output is correct
20 Correct 1567 ms 12664 KB Output is correct
21 Correct 332 ms 5792 KB Output is correct
22 Correct 1799 ms 17016 KB Output is correct
23 Correct 287 ms 31096 KB Output is correct
24 Correct 1110 ms 21368 KB Output is correct
25 Correct 2059 ms 32504 KB Output is correct
26 Correct 1702 ms 32632 KB Output is correct
27 Correct 1707 ms 32120 KB Output is correct
28 Runtime error 791 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 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 384 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 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 711 ms 21240 KB Output is correct
13 Correct 549 ms 21192 KB Output is correct
14 Correct 761 ms 18752 KB Output is correct
15 Correct 782 ms 18492 KB Output is correct
16 Correct 590 ms 13292 KB Output is correct
17 Correct 829 ms 18620 KB Output is correct
18 Correct 794 ms 18212 KB Output is correct
19 Correct 1274 ms 25824 KB Output is correct
20 Correct 1777 ms 12784 KB Output is correct
21 Correct 351 ms 5752 KB Output is correct
22 Correct 2277 ms 16968 KB Output is correct
23 Correct 312 ms 31224 KB Output is correct
24 Correct 1308 ms 21420 KB Output is correct
25 Correct 2486 ms 32552 KB Output is correct
26 Correct 1839 ms 32724 KB Output is correct
27 Correct 1916 ms 32100 KB Output is correct
28 Runtime error 969 ms 256000 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -