oj.uz

Submission #1082450

# Submission time Handle Problem Language Result Execution time Memory
1082450 2024-08-31T11:11:19 Z mindiyak Game (IOI13_game) C++14
10 / 100
 13000 ms 143396 KB 
#include "game.h"
#include <iostream>
#include <vector>

#define ll long long

using namespace std;

int r,c;
ll grid[2005][9005];

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;
}

void init(int R, int C) {
    r = R;c = C;
    for(int i=0;i<2005;i++)for(int j=0;j<9005;j++)grid[i][j] = 0;
}

void updater(int i,int pos,int l,int r,int idx,ll k){
    if(l == r){
        grid[i][pos] = k;
        return;
    }   
    int mid = (l+r)/2;
    if(idx<=mid){
        updater(i,2*pos+1,l,mid,idx,k);
    }else{
        updater(i,2*pos+2,mid+1,r,idx,k);
    }
    grid[i][pos] = gcd2(grid[i][2*pos+1],grid[i][2*pos+2]);
}

ll asker(int i,int pos,int l,int r,int ql,int qr){
    if(ql>r || qr<l)return 0;
    if(ql <= l && r <= qr){
        return grid[i][pos];
    }   
    int mid = (l+r)/2;
    return gcd2(asker(i,2*pos+1,l,mid,ql,qr),asker(i,2*pos+2,mid+1,r,ql,qr));
}

void update(int P, int Q, long long K) {
    updater(P,0,0,c-1,Q,K);
}

long long calculate(int P, int Q, int U, int V) {
    ll val = 0;
    for(int i=P;i<=U;i++){
        val = gcd2(val,asker(i,0,0,c-1,Q,V));
    }
    return val;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 141648 KB Output is correct
2 Correct 68 ms 141728 KB Output is correct
3 Correct 70 ms 141652 KB Output is correct
4 Correct 56 ms 141652 KB Output is correct
5 Correct 61 ms 141724 KB Output is correct
6 Correct 55 ms 141648 KB Output is correct
7 Correct 71 ms 141516 KB Output is correct
8 Correct 63 ms 141652 KB Output is correct
9 Correct 57 ms 141648 KB Output is correct
10 Correct 60 ms 141648 KB Output is correct
11 Correct 60 ms 141584 KB Output is correct
12 Correct 61 ms 141652 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 141648 KB Output is correct
2 Correct 63 ms 141648 KB Output is correct
3 Correct 73 ms 141648 KB Output is correct
4 Incorrect 655 ms 142164 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 141652 KB Output is correct
2 Correct 58 ms 141648 KB Output is correct
3 Correct 62 ms 141648 KB Output is correct
4 Correct 63 ms 141652 KB Output is correct
5 Correct 63 ms 141544 KB Output is correct
6 Correct 62 ms 141584 KB Output is correct
7 Correct 62 ms 141504 KB Output is correct
8 Correct 72 ms 141708 KB Output is correct
9 Correct 75 ms 141652 KB Output is correct
10 Correct 63 ms 141652 KB Output is correct
11 Correct 61 ms 141576 KB Output is correct
12 Execution timed out 13098 ms 143396 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 141648 KB Output is correct
2 Correct 62 ms 141680 KB Output is correct
3 Correct 61 ms 141552 KB Output is correct
4 Correct 63 ms 141648 KB Output is correct
5 Correct 75 ms 141580 KB Output is correct
6 Correct 63 ms 141724 KB Output is correct
7 Correct 60 ms 141648 KB Output is correct
8 Correct 61 ms 141652 KB Output is correct
9 Correct 62 ms 141660 KB Output is correct
10 Correct 63 ms 141676 KB Output is correct
11 Correct 76 ms 141648 KB Output is correct
12 Incorrect 650 ms 142204 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 141520 KB Output is correct
2 Correct 65 ms 141648 KB Output is correct
3 Correct 62 ms 141648 KB Output is correct
4 Correct 59 ms 141700 KB Output is correct
5 Correct 63 ms 141648 KB Output is correct
6 Correct 65 ms 141648 KB Output is correct
7 Correct 75 ms 141652 KB Output is correct
8 Correct 62 ms 141652 KB Output is correct
9 Correct 59 ms 141648 KB Output is correct
10 Correct 71 ms 141648 KB Output is correct
11 Correct 59 ms 141728 KB Output is correct
12 Incorrect 731 ms 142432 KB Output isn't correct
13 Halted 0 ms 0 KB -