oj.uz

Submission #349638

# Submission time Handle Problem Language Result Execution time Memory
349638 2021-01-18T05:13:04 Z talant117408 Game (IOI13_game) C++17
63 / 100
 6830 ms 190428 KB 
#include <bits/stdc++.h>
#include "game.h"
#ifndef EVAL
#include "grader.cpp"
#endif

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) int((v).size())
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define OK cout << "OK" << endl;


ll gcd2(ll X, ll Y) {
    ll tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

void pankov(){
    exit(0);
}

int n, m;
int type;

ll tree[103][400003];
ll tree2[8003][8003];

void update_tree(int v, int l, int r, int i, int pos, ll val){
    if(l == r){
        tree[i][v] = val;
        return;
    }
    int mid = (l+r) >> 1;
    if(pos <= mid) update_tree(v<<1, l, mid, i, pos, val);
    else update_tree((v<<1)+1, mid+1, r, i, pos, val);
    tree[i][v] = gcd2(tree[i][v<<1], tree[i][(v<<1)+1]);
}

ll get(int v, int l, int r, int i, int ql, int qr){
    if(l > qr || ql > r) return 0;
    if(ql <= l && r <= qr) return tree[i][v];
    int mid = (l+r) >> 1;
    return gcd2(get(v<<1, l, mid, i, ql, qr), get((v<<1)+1, mid+1, r, i, ql, qr));
}

void update_tree3(int v, int l, int r, int i, int pos, ll val){
    if(l == r){
        tree2[i][v] = val;
        return ;
    }
    int mid = (l+r) >> 1;
    if(pos <= mid) update_tree3(v<<1, l, mid, i, pos, val);
    else update_tree3((v<<1)+1, mid+1, r, i, pos, val);
    tree2[i][v] = gcd2(tree2[i][v<<1], tree2[i][(v<<1)+1]);
}

void update_tree2(int v, int l, int r, int i, int pos, ll val){
    if(l == r){
        update_tree3(1, 1, m, v, pos, val);
        return;
    }
    int mid = (l+r) >> 1;
    if(i <= mid) update_tree2(v<<1, l, mid, i, pos, val);
    else update_tree2((v<<1)+1, mid+1, r, i, pos, val);
    for(int j = 0; j < 8003; j++) tree2[v][j] = gcd2(tree2[v<<1][j], tree2[(v<<1)+1][j]);
}

ll get3(int v, int l, int r, int i, int ql, int qr){
    if(l > qr || ql > r) return 0;
    if(ql <= l && r <= qr) return tree2[i][v];
    int mid = (l+r) >> 1;
    return gcd2(get3(v<<1, l, mid, i, ql, qr), get3((v<<1)+1, mid+1, r, i, ql, qr));
}

ll get2(int v, int l, int r, int ql, int qr, int y1, int y2){
    if(l > qr || ql > r) return 0;
    if(ql <= l && r <= qr) return get3(1, 1, m, v, y1, y2);
    int mid = (l+r) >> 1;
    return gcd2(get2(v<<1, l, mid, ql, qr, y1, y2), get2((v<<1)+1, mid+1, r, ql, qr, y1, y2));
}

void init(int r, int c) {
    n = r, m = c;
    if(n <= 2000 && m <= 2000) type = 2;
    else if(n <= 100 && m <= 100000) type = 1;
    else pankov();
}

void update(int P, int Q, ll K) {
    P++, Q++;
    if(type == 1)
        update_tree(1, 1, m, P, Q, K);
    else
        update_tree2(1, 1, n, P, Q, K);
}

ll calculate(int x1, int y1, int x2, int y2) {
    x1++, y1++, x2++, y2++;
    if(type == 1){
        ll ans = 0;
        for(int i = x1; i <= x2; i++){
            ans = gcd2(ans, get(1, 1, m, i, y1, y2));
        }
        return ans;
    }
    else{
        return get2(1, 1, n, x1, x2, y1, y2);
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 14 ms 6508 KB Output is correct
3 Correct 14 ms 6508 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 14 ms 6508 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 1260 KB Output is correct
9 Correct 13 ms 6380 KB Output is correct
10 Correct 6 ms 4844 KB Output is correct
11 Correct 6 ms 1900 KB Output is correct
12 Correct 1 ms 364 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1119 ms 20808 KB Output is correct
5 Correct 655 ms 21100 KB Output is correct
6 Correct 876 ms 21504 KB Output is correct
7 Correct 891 ms 21484 KB Output is correct
8 Correct 739 ms 19844 KB Output is correct
9 Correct 904 ms 21100 KB Output is correct
10 Correct 823 ms 20716 KB Output is correct
11 Correct 1 ms 364 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 14 ms 6508 KB Output is correct
3 Correct 14 ms 6508 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 14 ms 6508 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 2 ms 1260 KB Output is correct
9 Correct 13 ms 6380 KB Output is correct
10 Correct 7 ms 4844 KB Output is correct
11 Correct 6 ms 1900 KB Output is correct
12 Correct 2767 ms 90352 KB Output is correct
13 Correct 3297 ms 83860 KB Output is correct
14 Correct 2179 ms 13164 KB Output is correct
15 Correct 3932 ms 164328 KB Output is correct
16 Correct 4955 ms 189012 KB Output is correct
17 Correct 3250 ms 176236 KB Output is correct
18 Correct 6288 ms 190276 KB Output is correct
19 Correct 6219 ms 190256 KB Output is correct
20 Correct 6811 ms 189604 KB Output is correct
21 Correct 1 ms 364 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 14 ms 6508 KB Output is correct
3 Correct 14 ms 6508 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 14 ms 6508 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 2 ms 1260 KB Output is correct
9 Correct 13 ms 6380 KB Output is correct
10 Correct 7 ms 4844 KB Output is correct
11 Correct 6 ms 1900 KB Output is correct
12 Correct 1136 ms 20748 KB Output is correct
13 Correct 661 ms 21228 KB Output is correct
14 Correct 875 ms 21528 KB Output is correct
15 Correct 914 ms 21356 KB Output is correct
16 Correct 762 ms 20076 KB Output is correct
17 Correct 888 ms 21228 KB Output is correct
18 Correct 859 ms 20972 KB Output is correct
19 Correct 2814 ms 90424 KB Output is correct
20 Correct 3271 ms 83804 KB Output is correct
21 Correct 2185 ms 13220 KB Output is correct
22 Correct 3982 ms 164228 KB Output is correct
23 Correct 4957 ms 188876 KB Output is correct
24 Correct 3225 ms 176312 KB Output is correct
25 Correct 6206 ms 190120 KB Output is correct
26 Correct 6424 ms 190336 KB Output is correct
27 Correct 6809 ms 189660 KB Output is correct
28 Incorrect 1 ms 364 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 14 ms 6508 KB Output is correct
3 Correct 15 ms 6508 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 16 ms 6508 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 2 ms 1260 KB Output is correct
9 Correct 13 ms 6380 KB Output is correct
10 Correct 7 ms 4864 KB Output is correct
11 Correct 6 ms 1900 KB Output is correct
12 Correct 1111 ms 21484 KB Output is correct
13 Correct 666 ms 21728 KB Output is correct
14 Correct 885 ms 22124 KB Output is correct
15 Correct 936 ms 21868 KB Output is correct
16 Correct 753 ms 20460 KB Output is correct
17 Correct 907 ms 21740 KB Output is correct
18 Correct 820 ms 21356 KB Output is correct
19 Correct 2819 ms 90508 KB Output is correct
20 Correct 3297 ms 84104 KB Output is correct
21 Correct 2175 ms 13420 KB Output is correct
22 Correct 3956 ms 164392 KB Output is correct
23 Correct 4977 ms 188676 KB Output is correct
24 Correct 3239 ms 176220 KB Output is correct
25 Correct 6189 ms 190428 KB Output is correct
26 Correct 6246 ms 190260 KB Output is correct
27 Correct 6830 ms 189504 KB Output is correct
28 Incorrect 1 ms 364 KB Output isn't correct
29 Halted 0 ms 0 KB -