oj.uz

Submission #1082444

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

#define ll long long

using namespace std;

int r,c;
ll grid[2001][10001];

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<2001;i++)for(int j=0;j<10001;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 53 ms 157008 KB Output is correct
2 Correct 55 ms 157008 KB Output is correct
3 Correct 52 ms 156840 KB Output is correct
4 Correct 65 ms 157012 KB Output is correct
5 Correct 64 ms 157008 KB Output is correct
6 Correct 54 ms 156932 KB Output is correct
7 Correct 53 ms 157008 KB Output is correct
8 Correct 59 ms 156952 KB Output is correct
9 Correct 52 ms 157012 KB Output is correct
10 Correct 54 ms 157012 KB Output is correct
11 Correct 53 ms 157008 KB Output is correct
12 Correct 53 ms 157012 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 156968 KB Output is correct
2 Correct 57 ms 157012 KB Output is correct
3 Correct 55 ms 157012 KB Output is correct
4 Incorrect 673 ms 161968 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 157008 KB Output is correct
2 Correct 55 ms 157008 KB Output is correct
3 Correct 55 ms 157012 KB Output is correct
4 Correct 50 ms 157008 KB Output is correct
5 Correct 61 ms 157008 KB Output is correct
6 Correct 55 ms 157012 KB Output is correct
7 Correct 58 ms 157012 KB Output is correct
8 Correct 54 ms 157008 KB Output is correct
9 Correct 47 ms 157016 KB Output is correct
10 Correct 52 ms 157008 KB Output is correct
11 Correct 54 ms 156856 KB Output is correct
12 Execution timed out 13098 ms 160836 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 157012 KB Output is correct
2 Correct 55 ms 156916 KB Output is correct
3 Correct 56 ms 157012 KB Output is correct
4 Correct 56 ms 157036 KB Output is correct
5 Correct 53 ms 157048 KB Output is correct
6 Correct 53 ms 157024 KB Output is correct
7 Correct 66 ms 157012 KB Output is correct
8 Correct 51 ms 156836 KB Output is correct
9 Correct 50 ms 157008 KB Output is correct
10 Correct 59 ms 156908 KB Output is correct
11 Correct 48 ms 156840 KB Output is correct
12 Incorrect 650 ms 162132 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 157012 KB Output is correct
2 Correct 50 ms 156928 KB Output is correct
3 Correct 55 ms 157028 KB Output is correct
4 Correct 58 ms 156856 KB Output is correct
5 Correct 50 ms 157008 KB Output is correct
6 Correct 55 ms 156984 KB Output is correct
7 Correct 52 ms 157008 KB Output is correct
8 Correct 64 ms 157012 KB Output is correct
9 Correct 56 ms 157008 KB Output is correct
10 Correct 53 ms 157012 KB Output is correct
11 Correct 58 ms 157016 KB Output is correct
12 Incorrect 640 ms 162112 KB Output isn't correct
13 Halted 0 ms 0 KB -