oj.uz

Submission #400251

# Submission time Handle Problem Language Result Execution time Memory
400251 2021-05-07T18:12:06 Z Antekb Game (IOI13_game) C++14
80 / 100
 4848 ms 256004 KB 
#include "game.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N=(1<<30), M=21142005, K=682005;

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 wsk1=1;
int l1[M], r1[M];
ll val1[M];

void upd(int v){
    if(!v)return;
    val1[v]=gcd2(val1[l1[v]], val1[r1[v]]);
}
ll quer1d(int v, int L, int R, int l, int r){
    if(!v)return 0;
    //cout<<L<<" "<<R<<" "<<v->val<<"q\n";
    if(l==L && r==R){
        return val1[v];
    }
    int M=(L+R)>>1;
    ll ans=0;
    if(l<=M)ans=gcd2(ans, quer1d(l1[v], L, M, l, min(M, r)));
    if(r>M)ans=gcd2(ans, quer1d(r1[v], M+1, R, max(l, M+1), r));
    return ans;
}
int upd1d(int v, int L, int R, int i, ll val){
    if(!v)v=wsk1++;
    if(L==R){
        //cout<<v->val<<" "<<val<<" "<<i<<"u\n";
        val1[v]=val;
        return v;
    }
    //cout<<L<<" "<<R<<" "<<v->val<<"a\n";
    int M=(L+R)>>1;
    if(i<=M)l1[v]=upd1d(l1[v], L, M, i, val);
    else r1[v]=upd1d(r1[v], M+1, R, i, val);
    upd(v);
    //cout<<L<<" "<<R<<" "<<v->val<<"b\n";
    return v;
}

int wsk2=1;
int l2[K], r2[K], val2[K];

ll quer2d(int v, int L, int R, int l, int r, int x, int y){
    if(!v)return 0;
    if(l==L && r==R){
        return quer1d(val2[v], 0, N-1, x, y);
    }
    int M=(L+R)>>1;
    ll ans=0;
    if(l<=M)ans=gcd2(ans, quer2d(l2[v], L, M, l, min(M, r), x, y));
    if(r>M)ans=gcd2(ans, quer2d(r2[v], M+1, R, max(l, M+1), r, x, y));
    return ans;
}

int upd2d(int v, int L, int R, int i, int j, ll val){
    if(!v)v=wsk2++;
    if(L==R){
        val2[v]=upd1d(val2[v], 0, N-1, j, val);
        return v;
    }
    int M=(L+R)>>1;
    if(i<=M)l2[v]=upd2d(l2[v], L, M, i, j, val);
    else r2[v]=upd2d(r2[v], M+1, R, i, j, val);
    val2[v]=upd1d(val2[v], 0, N-1, j, gcd2(quer1d(val2[l2[v]], 0, N-1, j, j), quer1d(val2[r2[v]], 0, N-1, j, j)));
    return v;
}
int root=0;
void init(int R, int C) {
    /* ... */
}

void update(int P, int Q, long long K) {
    root=upd2d(root, 0, N-1, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    return quer2d(root, 0, N-1, P, U, Q, V);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 3 ms 460 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1002 ms 27996 KB Output is correct
5 Correct 791 ms 28200 KB Output is correct
6 Correct 958 ms 25188 KB Output is correct
7 Correct 1014 ms 24960 KB Output is correct
8 Correct 642 ms 16196 KB Output is correct
9 Correct 989 ms 25168 KB Output is correct
10 Correct 949 ms 24752 KB Output is correct
11 Correct 1 ms 332 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 3 ms 460 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 1624 ms 12188 KB Output is correct
13 Correct 2174 ms 5752 KB Output is correct
14 Correct 673 ms 1852 KB Output is correct
15 Correct 2395 ms 8020 KB Output is correct
16 Correct 807 ms 13020 KB Output is correct
17 Correct 1158 ms 9764 KB Output is correct
18 Correct 1892 ms 13264 KB Output is correct
19 Correct 1652 ms 13544 KB Output is correct
20 Correct 1596 ms 12688 KB Output is correct
21 Correct 1 ms 332 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 3 ms 460 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 994 ms 27972 KB Output is correct
13 Correct 817 ms 28308 KB Output is correct
14 Correct 936 ms 25260 KB Output is correct
15 Correct 991 ms 24948 KB Output is correct
16 Correct 650 ms 16192 KB Output is correct
17 Correct 976 ms 25128 KB Output is correct
18 Correct 947 ms 24720 KB Output is correct
19 Correct 1595 ms 12272 KB Output is correct
20 Correct 2135 ms 5776 KB Output is correct
21 Correct 678 ms 2048 KB Output is correct
22 Correct 2404 ms 8008 KB Output is correct
23 Correct 830 ms 12868 KB Output is correct
24 Correct 1174 ms 9668 KB Output is correct
25 Correct 1838 ms 13376 KB Output is correct
26 Correct 1649 ms 13456 KB Output is correct
27 Correct 1594 ms 12856 KB Output is correct
28 Correct 831 ms 126976 KB Output is correct
29 Correct 2080 ms 141596 KB Output is correct
30 Correct 4826 ms 102596 KB Output is correct
31 Correct 4645 ms 78668 KB Output is correct
32 Correct 650 ms 1568 KB Output is correct
33 Correct 810 ms 2872 KB Output is correct
34 Correct 953 ms 138932 KB Output is correct
35 Correct 1367 ms 71184 KB Output is correct
36 Correct 2804 ms 139148 KB Output is correct
37 Correct 2221 ms 139332 KB Output is correct
38 Correct 2234 ms 138620 KB Output is correct
39 Correct 1847 ms 107140 KB Output is correct
40 Correct 1 ms 332 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 304 KB Output is correct
9 Correct 3 ms 460 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 2 ms 336 KB Output is correct
12 Correct 982 ms 28088 KB Output is correct
13 Correct 793 ms 28356 KB Output is correct
14 Correct 938 ms 25280 KB Output is correct
15 Correct 981 ms 25028 KB Output is correct
16 Correct 632 ms 16276 KB Output is correct
17 Correct 990 ms 25156 KB Output is correct
18 Correct 951 ms 24836 KB Output is correct
19 Correct 1618 ms 12528 KB Output is correct
20 Correct 2151 ms 5852 KB Output is correct
21 Correct 679 ms 1864 KB Output is correct
22 Correct 2439 ms 8220 KB Output is correct
23 Correct 798 ms 12928 KB Output is correct
24 Correct 1163 ms 9764 KB Output is correct
25 Correct 1838 ms 13320 KB Output is correct
26 Correct 1631 ms 13572 KB Output is correct
27 Correct 1589 ms 12844 KB Output is correct
28 Correct 823 ms 127140 KB Output is correct
29 Correct 2039 ms 141648 KB Output is correct
30 Correct 4848 ms 102596 KB Output is correct
31 Correct 4656 ms 78796 KB Output is correct
32 Correct 668 ms 1564 KB Output is correct
33 Correct 804 ms 3012 KB Output is correct
34 Correct 947 ms 138808 KB Output is correct
35 Correct 1365 ms 71032 KB Output is correct
36 Correct 2823 ms 139056 KB Output is correct
37 Correct 2261 ms 139224 KB Output is correct
38 Correct 2233 ms 138640 KB Output is correct
39 Runtime error 1282 ms 256004 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -