oj.uz

Submission #290080

# Submission time Handle Problem Language Result Execution time Memory
290080 2020-09-03T11:47:41 Z Atill83 Game (IOI13_game) C++14
63 / 100
 2045 ms 256000 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = (int) 2e3 + 5;
typedef long long ll;
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;
}

struct st{
    int l, r;
    vector<ll> t;
    
    void init(int ll, int rr, int C){
        l = ll;
        r = rr;
        t.resize(4*C, 0);
    }

    void upd(int v, int tl, int tr, int pos, ll val, vector<ll> &t1, vector<ll> &t2){
        if(l == r){
            if(tl == tr){
                t[v] = val;
            }else{
                int tm = (tl + tr) / 2;
                if(pos <= tm)
                    upd(2*v, tl, tm, pos, val, t1, t2);
                else upd(2*v + 1, tm + 1, tr, pos, val, t1, t2);
                t[v] = gcd2(t[2*v], t[2*v + 1]);
            }
        }else{
            if(tl == tr){
                t[v] = gcd2(t1[v], t2[v]);
            }else{
                int tm = (tl + tr) / 2;
                if(pos <= tm)
                    upd(2*v, tl, tm, pos, val, t1, t2);
                else upd(2*v + 1, tm + 1, tr, pos, val, t1, t2);
                t[v] = gcd2(t1[v], t2[v]);
            }
        }
    }
    ll que(int v, int tl, int tr, int l, int r){
        if(l > r) return -1;
        else if(tl == l && tr == r){
            return t[v];
        }else{
            int tm = (tl + tr) / 2;
            ll ans1 = que(2*v, tl, tm, l, min(tm, r)), ans2 = que(2*v + 1, tm + 1, tr, max(tm + 1, l), r);
            if(ans1 == -1) return ans2;
            else if(ans2 == -1) return ans1;
            else return gcd2(ans1, ans2);
        }
    }
} t[4*MAXN];
int c, r;
void build(int v, int tl, int tr){
    if(tl == tr){
        t[v].init(tl, tr, c);
    }else{
        int tm = (tl + tr) / 2;
        build(2*v, tl, tm);
        build(2*v+1, tm + 1, tr);
        t[v].init(tl, tr, c);
    }
}


void upd(int v, int tl, int tr, int posX, int posY, ll val){
    if(tl == tr){
        t[v].upd(1, 0, c - 1, posY, val, t[v].t, t[v].t);
    }else{
        int tm = (tl + tr) / 2;
        if(posX <= tm) upd(2*v, tl, tm, posX, posY, val);
        else upd(2*v+1, tm + 1, tr, posX, posY, val);
        t[v].upd(1, 0, c - 1, posY, val, t[2*v].t, t[2*v + 1].t);
    }
}

ll que(int v, int tl, int tr, int l1, int r1, int l2, int r2){
    if(l1 > r1) return -1;
    else if(tl == l1 && tr == r1){
        return t[v].que(1, 0, c - 1, l2, r2);
    }else{
        int tm = (tl + tr) / 2;
        ll ans1 = que(2*v, tl, tm, l1, min(tm, r1), l2, r2), ans2 = que(2*v + 1, tm + 1, tr, max(tm + 1, l1), r1, l2, r2);
        if(ans1 == -1) return ans2;
        else if(ans2 == -1) return ans1;
        else return gcd2(ans1, ans2);
    }
}



void init(int R, int C) {
    c = C;
    r = R;
    build(1, 0, R - 1);
}

void update(int P, int Q, long long K) {
    upd(1, 0, r - 1, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    return que(1, 0, r - 1, 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 512 KB Output is correct
2 Correct 1 ms 1152 KB Output is correct
3 Correct 1 ms 1152 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 1152 KB Output is correct
6 Correct 1 ms 1152 KB Output is correct
7 Correct 1 ms 640 KB Output is correct
8 Correct 1 ms 768 KB Output is correct
9 Correct 1 ms 1152 KB Output is correct
10 Correct 2 ms 1152 KB Output is correct
11 Correct 1 ms 1152 KB Output is correct
12 Correct 1 ms 512 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 891 ms 64376 KB Output is correct
5 Correct 585 ms 64504 KB Output is correct
6 Correct 772 ms 61260 KB Output is correct
7 Correct 768 ms 61048 KB Output is correct
8 Correct 675 ms 61848 KB Output is correct
9 Correct 779 ms 61048 KB Output is correct
10 Correct 734 ms 60808 KB Output is correct
11 Correct 1 ms 512 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 1152 KB Output is correct
3 Correct 1 ms 1152 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 1152 KB Output is correct
6 Correct 1 ms 1152 KB Output is correct
7 Correct 1 ms 640 KB Output is correct
8 Correct 1 ms 768 KB Output is correct
9 Correct 1 ms 1152 KB Output is correct
10 Correct 1 ms 1152 KB Output is correct
11 Correct 1 ms 1152 KB Output is correct
12 Correct 1082 ms 67600 KB Output is correct
13 Correct 1494 ms 64036 KB Output is correct
14 Correct 998 ms 255152 KB Output is correct
15 Correct 1884 ms 255376 KB Output is correct
16 Correct 356 ms 255224 KB Output is correct
17 Correct 1826 ms 256000 KB Output is correct
18 Correct 2033 ms 255632 KB Output is correct
19 Correct 2024 ms 255636 KB Output is correct
20 Correct 1945 ms 255184 KB Output is correct
21 Correct 1 ms 512 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 2 ms 1152 KB Output is correct
3 Correct 1 ms 1152 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 1152 KB Output is correct
6 Correct 1 ms 1152 KB Output is correct
7 Correct 1 ms 640 KB Output is correct
8 Correct 1 ms 768 KB Output is correct
9 Correct 1 ms 1152 KB Output is correct
10 Correct 1 ms 1152 KB Output is correct
11 Correct 1 ms 1152 KB Output is correct
12 Correct 884 ms 64352 KB Output is correct
13 Correct 598 ms 64632 KB Output is correct
14 Correct 795 ms 61292 KB Output is correct
15 Correct 776 ms 61048 KB Output is correct
16 Correct 666 ms 61692 KB Output is correct
17 Correct 762 ms 61048 KB Output is correct
18 Correct 728 ms 60708 KB Output is correct
19 Correct 1056 ms 67320 KB Output is correct
20 Correct 1504 ms 63992 KB Output is correct
21 Correct 1025 ms 255128 KB Output is correct
22 Correct 1911 ms 255528 KB Output is correct
23 Correct 368 ms 255224 KB Output is correct
24 Correct 1818 ms 255840 KB Output is correct
25 Correct 2035 ms 255712 KB Output is correct
26 Correct 2039 ms 255728 KB Output is correct
27 Correct 1974 ms 255096 KB Output is correct
28 Runtime error 1 ms 896 KB Execution killed with signal 11
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 1152 KB Output is correct
3 Correct 1 ms 1152 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 1152 KB Output is correct
6 Correct 1 ms 1152 KB Output is correct
7 Correct 1 ms 640 KB Output is correct
8 Correct 1 ms 768 KB Output is correct
9 Correct 1 ms 1152 KB Output is correct
10 Correct 1 ms 1152 KB Output is correct
11 Correct 1 ms 1152 KB Output is correct
12 Correct 875 ms 64248 KB Output is correct
13 Correct 583 ms 64504 KB Output is correct
14 Correct 770 ms 61304 KB Output is correct
15 Correct 766 ms 61048 KB Output is correct
16 Correct 672 ms 61944 KB Output is correct
17 Correct 775 ms 61128 KB Output is correct
18 Correct 725 ms 60992 KB Output is correct
19 Correct 1066 ms 67236 KB Output is correct
20 Correct 1499 ms 64108 KB Output is correct
21 Correct 1012 ms 254840 KB Output is correct
22 Correct 1903 ms 254956 KB Output is correct
23 Correct 360 ms 254840 KB Output is correct
24 Correct 1804 ms 255420 KB Output is correct
25 Correct 2045 ms 255308 KB Output is correct
26 Correct 2016 ms 255484 KB Output is correct
27 Correct 1959 ms 254868 KB Output is correct
28 Runtime error 1 ms 896 KB Execution killed with signal 11
29 Halted 0 ms 0 KB -