oj.uz

Submission #400237

# Submission time Handle Problem Language Result Execution time Memory
400237 2021-05-07T17:49:36 Z Antekb Game (IOI13_game) C++14
63 / 100
 2338 ms 256004 KB 
#include "game.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N=(1<<30);

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 node{
    ll val=0;
    node* l=nullptr, *r=nullptr;
    node(ll _val): val(_val){}
};
ll val(node* v){
    if(!v)return 0;
    return v->val;
}
void upd(node* v){
    if(!v)return;
    v->val=gcd2(val(v->l), val(v->r));
}
ll quer1d(node* 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 v->val;
    }
    int M=(L+R)>>1;
    ll ans=0;
    if(l<=M)ans=gcd2(ans, quer1d(v->l, L, M, l, min(M, r)));
    if(r>M)ans=gcd2(ans, quer1d(v->r, M+1, R, max(l, M+1), r));
    return ans;
}
node* upd1d(node* v, int L, int R, int i, ll val){
    if(!v)v=new node(0);
    if(L==R){
        //cout<<v->val<<" "<<val<<" "<<i<<"u\n";
        v->val=val;
        return v;
    }
    //cout<<L<<" "<<R<<" "<<v->val<<"a\n";
    int M=(L+R)>>1;
    if(i<=M)v->l=upd1d(v->l, L, M, i, val);
    else v->r=upd1d(v->r, M+1, R, i, val);
    upd(v);
    //cout<<L<<" "<<R<<" "<<v->val<<"b\n";
    return v;
}

struct node2{
    node* val=nullptr;
    node2* l=nullptr, *r=nullptr;
    node2(node* _v): val(_v){}
};
ll quer2d(node2* v, int L, int R, int l, int r, int x, int y){
    if(!v)return 0;
    if(l==L && r==R){
        return quer1d(v->val, 0, N-1, x, y);
    }
    int M=(L+R)>>1;
    ll ans=0;
    if(l<=M)ans=gcd2(ans, quer2d(v->l, L, M, l, min(M, r), x, y));
    if(r>M)ans=gcd2(ans, quer2d(v->r, M+1, R, max(l, M+1), r, x, y));
    return ans;
}
node* Val(node2* v){
    if(!v)return 0;
    return v->val;
}
node2* upd2d(node2* v, int L, int R, int i, int j, ll val){
    if(!v)v=new node2(nullptr);
    if(L==R){
        v->val=upd1d(v->val, 0, N-1, j, val);
        return v;
    }
    int M=(L+R)>>1;
    if(i<=M)v->l=upd2d(v->l, L, M, i, j, val);
    else v->r=upd2d(v->r, M+1, R, i, j, val);
    v->val=upd1d(v->val, 0, N-1, j, gcd2(quer1d(Val(v->l), 0, N-1, j, j), quer1d(Val(v->r), 0, N-1, j, j)));
    return v;
}
node2* root=nullptr;
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 336 KB Output is correct
2 Correct 3 ms 588 KB Output is correct
3 Correct 3 ms 588 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 588 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 1 ms 292 KB Output is correct
9 Correct 3 ms 588 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 3 ms 424 KB Output is correct
12 Correct 2 ms 332 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 300 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 296 KB Output is correct
4 Correct 1016 ms 54316 KB Output is correct
5 Correct 829 ms 54032 KB Output is correct
6 Correct 986 ms 51884 KB Output is correct
7 Correct 998 ms 51604 KB Output is correct
8 Correct 683 ms 33036 KB Output is correct
9 Correct 1000 ms 51824 KB Output is correct
10 Correct 984 ms 51316 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 588 KB Output is correct
3 Correct 5 ms 588 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 3 ms 588 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 588 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 1545 ms 22408 KB Output is correct
13 Correct 2075 ms 12964 KB Output is correct
14 Correct 655 ms 5820 KB Output is correct
15 Correct 2307 ms 17776 KB Output is correct
16 Correct 782 ms 27136 KB Output is correct
17 Correct 1244 ms 21028 KB Output is correct
18 Correct 1984 ms 28808 KB Output is correct
19 Correct 1804 ms 28796 KB Output is correct
20 Correct 1711 ms 28152 KB Output is correct
21 Correct 1 ms 332 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 284 KB Output is correct
2 Correct 3 ms 588 KB Output is correct
3 Correct 3 ms 588 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 3 ms 716 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 588 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 1008 ms 54300 KB Output is correct
13 Correct 834 ms 54032 KB Output is correct
14 Correct 1006 ms 51876 KB Output is correct
15 Correct 1022 ms 51564 KB Output is correct
16 Correct 662 ms 32912 KB Output is correct
17 Correct 1039 ms 51856 KB Output is correct
18 Correct 988 ms 51584 KB Output is correct
19 Correct 1536 ms 22468 KB Output is correct
20 Correct 2084 ms 12676 KB Output is correct
21 Correct 650 ms 5760 KB Output is correct
22 Correct 2338 ms 17636 KB Output is correct
23 Correct 800 ms 27160 KB Output is correct
24 Correct 1336 ms 21104 KB Output is correct
25 Correct 2142 ms 28560 KB Output is correct
26 Correct 1893 ms 28848 KB Output is correct
27 Correct 1787 ms 28248 KB Output is correct
28 Correct 1090 ms 256000 KB Output is correct
29 Runtime error 1920 ms 256004 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 5 ms 548 KB Output is correct
3 Correct 5 ms 588 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 588 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 588 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 1020 ms 54272 KB Output is correct
13 Correct 830 ms 54332 KB Output is correct
14 Correct 1036 ms 51856 KB Output is correct
15 Correct 1049 ms 51536 KB Output is correct
16 Correct 682 ms 32920 KB Output is correct
17 Correct 1054 ms 51780 KB Output is correct
18 Correct 1000 ms 51396 KB Output is correct
19 Correct 1561 ms 22364 KB Output is correct
20 Correct 2091 ms 12784 KB Output is correct
21 Correct 643 ms 5956 KB Output is correct
22 Correct 2307 ms 17712 KB Output is correct
23 Correct 797 ms 27264 KB Output is correct
24 Correct 1315 ms 20912 KB Output is correct
25 Correct 2138 ms 28720 KB Output is correct
26 Correct 1873 ms 28808 KB Output is correct
27 Correct 1802 ms 28472 KB Output is correct
28 Correct 1054 ms 256000 KB Output is correct
29 Runtime error 1937 ms 256004 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -