oj.uz

Submission #400247

# Submission time Handle Problem Language Result Execution time Memory
400247 2021-05-07T18:04:43 Z Antekb Game (IOI13_game) C++14
80 / 100
 4905 ms 256000 KB 
#include "game.h"
#include<bits/stdc++.h>

using namespace std;

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

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 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 1 ms 304 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 985 ms 27620 KB Output is correct
5 Correct 780 ms 27940 KB Output is correct
6 Correct 938 ms 24856 KB Output is correct
7 Correct 985 ms 24516 KB Output is correct
8 Correct 666 ms 15828 KB Output is correct
9 Correct 981 ms 24700 KB Output is correct
10 Correct 955 ms 24260 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 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 428 KB Output is correct
10 Correct 2 ms 424 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 1603 ms 11812 KB Output is correct
13 Correct 2151 ms 5556 KB Output is correct
14 Correct 673 ms 1504 KB Output is correct
15 Correct 2442 ms 7616 KB Output is correct
16 Correct 803 ms 12512 KB Output is correct
17 Correct 1201 ms 9340 KB Output is correct
18 Correct 1943 ms 12936 KB Output is correct
19 Correct 1708 ms 13168 KB Output is correct
20 Correct 1636 ms 12396 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 997 ms 27588 KB Output is correct
13 Correct 790 ms 27868 KB Output is correct
14 Correct 945 ms 24876 KB Output is correct
15 Correct 1002 ms 24504 KB Output is correct
16 Correct 646 ms 15940 KB Output is correct
17 Correct 984 ms 24668 KB Output is correct
18 Correct 956 ms 24252 KB Output is correct
19 Correct 1591 ms 11844 KB Output is correct
20 Correct 2194 ms 5424 KB Output is correct
21 Correct 674 ms 1588 KB Output is correct
22 Correct 2397 ms 7644 KB Output is correct
23 Correct 818 ms 12532 KB Output is correct
24 Correct 1166 ms 9252 KB Output is correct
25 Correct 1859 ms 12724 KB Output is correct
26 Correct 1679 ms 12996 KB Output is correct
27 Correct 1629 ms 12440 KB Output is correct
28 Correct 830 ms 126560 KB Output is correct
29 Correct 2021 ms 151304 KB Output is correct
30 Correct 4830 ms 108948 KB Output is correct
31 Correct 4838 ms 85012 KB Output is correct
32 Correct 664 ms 10240 KB Output is correct
33 Correct 824 ms 11548 KB Output is correct
34 Correct 963 ms 144924 KB Output is correct
35 Correct 1443 ms 80192 KB Output is correct
36 Correct 2902 ms 149180 KB Output is correct
37 Correct 2391 ms 149188 KB Output is correct
38 Correct 2336 ms 148784 KB Output is correct
39 Correct 1964 ms 116840 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 436 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 1014 ms 27668 KB Output is correct
13 Correct 790 ms 28072 KB Output is correct
14 Correct 938 ms 24840 KB Output is correct
15 Correct 997 ms 24644 KB Output is correct
16 Correct 652 ms 16000 KB Output is correct
17 Correct 1000 ms 24860 KB Output is correct
18 Correct 960 ms 24316 KB Output is correct
19 Correct 1616 ms 12072 KB Output is correct
20 Correct 2143 ms 5448 KB Output is correct
21 Correct 677 ms 1556 KB Output is correct
22 Correct 2425 ms 8004 KB Output is correct
23 Correct 806 ms 12644 KB Output is correct
24 Correct 1166 ms 9352 KB Output is correct
25 Correct 1964 ms 12920 KB Output is correct
26 Correct 1694 ms 13060 KB Output is correct
27 Correct 1635 ms 12484 KB Output is correct
28 Correct 825 ms 126532 KB Output is correct
29 Correct 2089 ms 151268 KB Output is correct
30 Correct 4905 ms 108884 KB Output is correct
31 Correct 4721 ms 85004 KB Output is correct
32 Correct 651 ms 10252 KB Output is correct
33 Correct 810 ms 11496 KB Output is correct
34 Correct 962 ms 145052 KB Output is correct
35 Correct 1424 ms 80392 KB Output is correct
36 Correct 2964 ms 149028 KB Output is correct
37 Correct 2386 ms 149320 KB Output is correct
38 Correct 2373 ms 148632 KB Output is correct
39 Runtime error 1345 ms 256000 KB Execution killed with signal 11
40 Halted 0 ms 0 KB -