oj.uz

Submission #250332

# Submission time Handle Problem Language Result Execution time Memory
250332 2020-07-17T12:21:52 Z MarcoMeijer Game (IOI13_game) C++14
63 / 100
 1617 ms 256004 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;

//macros
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define INF 1e9
#define pb push_back
#define fi first
#define se second
#define sz size()

int R, C;

ll gcd(ll X, ll Y) {
    ll tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

struct Seg {
    int bg, ed;
    ll val;
    Seg* ls=nullptr;
    Seg* rs=nullptr;

    Seg(int l, int r, ll v=0) {
        bg=l; ed=r; val=v;
    }
    ll f(Seg* s) {
        if(s == nullptr) return 0;
        return s->val;
    }
    ll f(Seg* s, int i, int j, int l, int r) {
        if(s == nullptr) return 0;
        return s->get(i,j,l,r);
    }
    void set(int i, ll v, int l, int r) {
        int m=(l+r)/2;
        if(l == r) {
            val = v;
            return;
        }
        if(i <= m) {
            if(ls == nullptr) ls = new Seg(l,m);
            ls->set(i,v,l,m);
        } else {
            if(rs == nullptr) rs = new Seg(m+1,r);
            rs->set(i,v,m+1,r);
        }
        val = gcd(f(ls), f(rs));
    }
    ll get(int i, int j, int l, int r) {
        if(j < l || i > r) return 0;
        if(i <= l && j >= r) return val;
        int m=(l+r)/2;
        ll a = f(ls,i,j,l,m);
        ll b = f(rs,i,j,m+1,r);
        return gcd(a,b);
    }
};


struct Seg2 {
    int bg, ed;
    Seg val;
    Seg2* ls=nullptr;
    Seg2* rs=nullptr;
    
    Seg2(int l, int r) : val(0,C-1) {
        bg = l; ed = r;
    }
    ll f(Seg2* s, int j) {
        if(s == nullptr) return 0;
        return s->val.get(j,j,0,C-1);
    }
    void set(int i, int j, ll v, int l, int r) {
        int m=(l+r)/2;
        if(l == r) {
            val.set(j,v,0,C-1);
            return;
        }
        if(i <= m) {
            if(ls == nullptr) ls = new Seg2(l,m);
            ls->set(i,j,v,l,m);
        } else {
            if(rs == nullptr) rs = new Seg2(m+1,r);
            rs->set(i,j,v,m+1,r);
        }
        ll nV = 0;
        nV = gcd(f(ls,j), f(rs,j));
        val.set(j,nV,0,C-1);
    }
    ll f(Seg2* s, int i, int j, int I, int J, int l, int r) {
        if(s == nullptr) return 0;
        return s->get(i,j,I,J,l,r);
    }
    ll get(int i, int j, int I, int J, int l, int r) {
        if(j < l || i > r) return 0;
        if(i <= l && j >= r) return val.get(I,J,0,C-1);
        int m=(l+r)/2;
        ll a = f(ls,i,j,I,J,l,m);
        ll b = f(rs,i,j,I,J,m+1,r);
        return gcd(a,b);
    }
};

Seg2* SEG;

void init(int _R, int _C) {
    R = _R;
    C = _C;
    SEG = new Seg2(0,R-1);
    //RE(i,R) SEG[i] = new Seg(0,C-1);
}

void update(int P, int Q, ll K) {
    SEG->set(P,Q,K,0,R-1);
    //SEG[P]->set(Q,K,0,C-1);
}

ll calculate(int P, int Q, int U, int V) {
    /*ll ans = 0;
    REP(i,P,U+1) ans = gcd(ans, SEG[i]->get(Q,V,0,C-1));
    return ans;*/
    return SEG->get(P,U,Q,V,0,R-1);
}

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 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 0 ms 256 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 578 ms 17016 KB Output is correct
5 Correct 382 ms 17272 KB Output is correct
6 Correct 568 ms 14328 KB Output is correct
7 Correct 667 ms 14072 KB Output is correct
8 Correct 419 ms 9080 KB Output is correct
9 Correct 619 ms 14136 KB Output is correct
10 Correct 589 ms 13560 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 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 834 ms 25568 KB Output is correct
13 Correct 1327 ms 12820 KB Output is correct
14 Correct 329 ms 5880 KB Output is correct
15 Correct 1546 ms 17048 KB Output is correct
16 Correct 307 ms 31096 KB Output is correct
17 Correct 915 ms 21248 KB Output is correct
18 Correct 1490 ms 32396 KB Output is correct
19 Correct 1524 ms 32708 KB Output is correct
20 Correct 1321 ms 32164 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 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 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 580 ms 16888 KB Output is correct
13 Correct 382 ms 17272 KB Output is correct
14 Correct 544 ms 14200 KB Output is correct
15 Correct 618 ms 14072 KB Output is correct
16 Correct 466 ms 9080 KB Output is correct
17 Correct 646 ms 14056 KB Output is correct
18 Correct 560 ms 13560 KB Output is correct
19 Correct 837 ms 25824 KB Output is correct
20 Correct 1321 ms 12844 KB Output is correct
21 Correct 332 ms 5752 KB Output is correct
22 Correct 1559 ms 16988 KB Output is correct
23 Correct 280 ms 30968 KB Output is correct
24 Correct 913 ms 21240 KB Output is correct
25 Correct 1596 ms 32520 KB Output is correct
26 Correct 1338 ms 32672 KB Output is correct
27 Correct 1303 ms 31944 KB Output is correct
28 Runtime error 746 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 1 ms 256 KB Output is correct
8 Correct 0 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 0 ms 384 KB Output is correct
12 Correct 587 ms 17040 KB Output is correct
13 Correct 379 ms 17144 KB Output is correct
14 Correct 552 ms 14328 KB Output is correct
15 Correct 613 ms 13976 KB Output is correct
16 Correct 442 ms 9248 KB Output is correct
17 Correct 625 ms 14072 KB Output is correct
18 Correct 561 ms 13560 KB Output is correct
19 Correct 824 ms 25652 KB Output is correct
20 Correct 1344 ms 12708 KB Output is correct
21 Correct 326 ms 5880 KB Output is correct
22 Correct 1586 ms 17088 KB Output is correct
23 Correct 280 ms 30968 KB Output is correct
24 Correct 891 ms 21368 KB Output is correct
25 Correct 1617 ms 32440 KB Output is correct
26 Correct 1544 ms 32736 KB Output is correct
27 Correct 1235 ms 32036 KB Output is correct
28 Runtime error 727 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -