oj.uz

Submission #349629

# Submission time Handle Problem Language Result Execution time Memory
349629 2021-01-18T04:21:14 Z talant117408 Game (IOI13_game) C++17
37 / 100
 1125 ms 26060 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;
}

int n, m;

ll tree[103][400003];

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 init(int r, int c) {
    n = r, m = c;
    if(n > 100) exit(0);
}

void update(int P, int Q, ll K) {
    P++, Q++;
    update_tree(1, 1, m, P, Q, K);
}

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 1004 KB Output is correct
3 Correct 1 ms 1004 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 748 KB Output is correct
6 Correct 1 ms 876 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 620 KB Output is correct
9 Correct 1 ms 1004 KB Output is correct
10 Correct 1 ms 876 KB Output is correct
11 Correct 1 ms 620 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 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1102 ms 20972 KB Output is correct
5 Correct 649 ms 21376 KB Output is correct
6 Correct 892 ms 21612 KB Output is correct
7 Correct 897 ms 21228 KB Output is correct
8 Correct 759 ms 19968 KB Output is correct
9 Correct 917 ms 21204 KB Output is correct
10 Correct 865 ms 20836 KB Output is correct
11 Correct 1 ms 364 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 1004 KB Output is correct
3 Correct 2 ms 1004 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 748 KB Output is correct
6 Correct 1 ms 876 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 620 KB Output is correct
9 Correct 1 ms 1004 KB Output is correct
10 Correct 1 ms 876 KB Output is correct
11 Correct 1 ms 620 KB Output is correct
12 Incorrect 1 ms 364 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 1004 KB Output is correct
3 Correct 1 ms 1004 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 748 KB Output is correct
6 Correct 1 ms 876 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 620 KB Output is correct
9 Correct 1 ms 1004 KB Output is correct
10 Correct 1 ms 896 KB Output is correct
11 Correct 1 ms 620 KB Output is correct
12 Correct 1125 ms 25068 KB Output is correct
13 Correct 640 ms 24960 KB Output is correct
14 Correct 875 ms 25964 KB Output is correct
15 Correct 921 ms 25708 KB Output is correct
16 Correct 747 ms 24044 KB Output is correct
17 Correct 917 ms 25964 KB Output is correct
18 Correct 859 ms 25580 KB Output is correct
19 Incorrect 1 ms 364 KB Output isn't correct
20 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 2 ms 1132 KB Output is correct
3 Correct 1 ms 1004 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 748 KB Output is correct
6 Correct 1 ms 876 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 620 KB Output is correct
9 Correct 1 ms 1004 KB Output is correct
10 Correct 1 ms 876 KB Output is correct
11 Correct 1 ms 620 KB Output is correct
12 Correct 1102 ms 24940 KB Output is correct
13 Correct 641 ms 24940 KB Output is correct
14 Correct 897 ms 26060 KB Output is correct
15 Correct 950 ms 25832 KB Output is correct
16 Correct 766 ms 24112 KB Output is correct
17 Correct 907 ms 25836 KB Output is correct
18 Correct 833 ms 25412 KB Output is correct
19 Incorrect 1 ms 364 KB Output isn't correct
20 Halted 0 ms 0 KB -