oj.uz

Submission #400250

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

using namespace std;

typedef long long ll;
const int N=(1<<30), M=2e7, K=660005;

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 4 ms 460 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 1 ms 304 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 436 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 995 ms 29212 KB Output is correct
5 Correct 788 ms 29592 KB Output is correct
6 Correct 964 ms 26392 KB Output is correct
7 Correct 988 ms 26124 KB Output is correct
8 Correct 650 ms 17340 KB Output is correct
9 Correct 1016 ms 26284 KB Output is correct
10 Correct 956 ms 25796 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 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 1636 ms 13520 KB Output is correct
13 Correct 2161 ms 7012 KB Output is correct
14 Correct 673 ms 3040 KB Output is correct
15 Correct 2446 ms 9340 KB Output is correct
16 Correct 824 ms 14192 KB Output is correct
17 Correct 1177 ms 10912 KB Output is correct
18 Correct 1894 ms 14436 KB Output is correct
19 Correct 1752 ms 14612 KB Output is correct
20 Correct 1597 ms 14044 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 4 ms 460 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 1 ms 336 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 989 ms 29300 KB Output is correct
13 Correct 787 ms 29472 KB Output is correct
14 Correct 934 ms 26440 KB Output is correct
15 Correct 966 ms 26172 KB Output is correct
16 Correct 636 ms 17348 KB Output is correct
17 Correct 969 ms 26496 KB Output is correct
18 Correct 935 ms 25856 KB Output is correct
19 Correct 1619 ms 13644 KB Output is correct
20 Correct 2148 ms 7064 KB Output is correct
21 Correct 681 ms 3016 KB Output is correct
22 Correct 2425 ms 9332 KB Output is correct
23 Correct 803 ms 14204 KB Output is correct
24 Correct 1183 ms 10948 KB Output is correct
25 Correct 1864 ms 14440 KB Output is correct
26 Correct 1659 ms 14544 KB Output is correct
27 Correct 1626 ms 14208 KB Output is correct
28 Correct 838 ms 128440 KB Output is correct
29 Correct 2031 ms 142120 KB Output is correct
30 Correct 4815 ms 102748 KB Output is correct
31 Correct 4645 ms 79032 KB Output is correct
32 Correct 662 ms 1652 KB Output is correct
33 Correct 821 ms 2944 KB Output is correct
34 Correct 954 ms 138976 KB Output is correct
35 Correct 1369 ms 71176 KB Output is correct
36 Correct 2834 ms 139352 KB Output is correct
37 Correct 2228 ms 139440 KB Output is correct
38 Correct 2238 ms 138696 KB Output is correct
39 Correct 1842 ms 107284 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 1 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 436 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 3 ms 416 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 428 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 979 ms 28628 KB Output is correct
13 Correct 771 ms 28840 KB Output is correct
14 Correct 948 ms 25688 KB Output is correct
15 Correct 988 ms 25388 KB Output is correct
16 Correct 661 ms 16792 KB Output is correct
17 Correct 969 ms 25812 KB Output is correct
18 Correct 963 ms 25304 KB Output is correct
19 Correct 1614 ms 12748 KB Output is correct
20 Correct 2127 ms 6200 KB Output is correct
21 Correct 672 ms 2320 KB Output is correct
22 Correct 2424 ms 8608 KB Output is correct
23 Correct 825 ms 13556 KB Output is correct
24 Correct 1176 ms 10308 KB Output is correct
25 Correct 1905 ms 13680 KB Output is correct
26 Correct 1680 ms 13908 KB Output is correct
27 Correct 1603 ms 13276 KB Output is correct
28 Correct 853 ms 127464 KB Output is correct
29 Correct 2059 ms 141736 KB Output is correct
30 Correct 4846 ms 102612 KB Output is correct
31 Correct 4668 ms 78768 KB Output is correct
32 Correct 652 ms 1604 KB Output is correct
33 Correct 825 ms 3012 KB Output is correct
34 Correct 963 ms 138852 KB Output is correct
35 Correct 1382 ms 71136 KB Output is correct
36 Correct 2844 ms 139012 KB Output is correct
37 Correct 2314 ms 139108 KB Output is correct
38 Correct 2289 ms 138564 KB Output is correct
39 Runtime error 1291 ms 256004 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -