oj.uz

답안 #1082444

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1082444 2024-08-31T11:04:55 Z mindiyak 게임 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -