oj.uz

답안 #65440

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
65440 2018-08-07T15:45:45 Z boook 게임 (IOI13_game) C++14
63 / 100
 10439 ms 257024 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define REP(i,j,k)     for(int i = j ; i < k ; ++i)
#define RREP(i,j,k)    for(int i = j ; i >=k ; --i)
#define A    first
#define B    second
#define mp   make_pair
#define pb   emplace_back
#define PII pair<long long , long long>
#define MEM(i,j)   memset(i , j , sizeof i)
#define ALL(i)     i.begin() , i.end()
#define DBGG(i,j)     cout << i << " " << j << endl
#define DB4(i,j,k,l)  cout << i << " " << j << " " << k << " " << l << endl
#define IOS cin.tie(0) , cout.sync_with_stdio(0)
#define endl "\n"
//------------------------------------------------------------
// #include "grader.h"
#include "game.h"
#define MAX 230000
#define INF 0x3f3f3f3f
#define mid (l + (r - l) / 2)

long long n , m;
long long sum[MAX * 40];
long long ls[MAX * 40] , rs[MAX * 40] , pos = 2;
long long GCD(long long a , long long b){
    // if(a && b) cout << a << " " << b << endl;
    return __gcd(a , b);
}
void init(int R, int C) {
    n = R , m = C;
}
void update2(long long now , long long l , long long r , long long x , long long y , long long val){
    assert(now != 0);
    if(l == r) sum[now] = val;// , DB4("now update" , l , now , val);
    else {
        if((y * n + x) <= mid + 0){
            if(ls[now] == 0) ls[now] = pos ++;
            update2(ls[now] , l , mid + 0 , x , y , val);
        }
        if(mid + 1 <= y * n + x){
            if(rs[now] == 0) rs[now] = pos ++;
            update2(rs[now] , mid + 1 , r , x , y , val);
        }
        sum[now] = GCD(sum[ls[now]] , sum[rs[now]]);
    }
    // DB4("now = " , sum[now] , sum[ls[now]] , sum[rs[now]]);
}
void update1(long long now , long long l , long long r , long long x , long long y , long long val){
    assert(now != 0);
    if(sum[now] == 0) sum[now] = pos ++;
    update2(sum[now] , 0 , m * n , x , y , val);
    if(l == r);
    else {
        if(x <= mid + 0){
            if(ls[now] == 0) ls[now] = pos ++;
            update1(ls[now] , l , mid + 0 , x , y , val);
        }
        if(mid + 1 <= x){
            if(rs[now] == 0) rs[now] = pos ++;
            update1(rs[now] , mid + 1 , r , x , y , val);
        }
    }
    
}
void update(int P, int Q, long long K) {
    if(pos >= MAX * 39) assert(0);
    update1(1 , 0 , n , P , Q , K);
}
long long query2(long long now , long long l , long long r , long long ql , long long qr){
    // DBGG("now = " , now);
    if(now == 0) return 0;
    if(ql <= l && r <= qr) return sum[now];
    else if(qr <= mid + 0) return query2(ls[now] , l , mid + 0 , ql , qr);
    else if(mid + 1 <= ql) return query2(rs[now] , mid + 1 , r , ql , qr);
    else GCD(query2(ls[now] , l , mid + 0 , ql , qr) , query2(rs[now] , mid + 1 , r , ql , qr));
}
long long query1(long long now , long long l , long long r , long long ql , long long qr , long long c , long long d){
    if(now == 0) return 0;
    if(ql <= l && r <= qr) return query2(sum[now] , 0 , m * n , c * n , d * n + n - 1);
    else if(qr <= mid + 0) return query1(ls[now] , l , mid + 0 , ql , qr , c , d);
    else if(mid + 1 <= ql) return query1(rs[now] , mid + 1 , r , ql , qr , c , d);
    return GCD(query1(ls[now] , l , mid + 0 , ql , qr , c , d)
               , query1(rs[now] , mid + 1 , r , ql , qr , c , d));
}
long long calculate(int P, int Q, int U, int V) {
    return query1(1 , 0 , n , P , U , Q , V);
}

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~
game.cpp: In function 'long long int query2(long long int, long long int, long long int, long long int, long long int)':
game.cpp:79:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 5 ms 716 KB Output is correct
3 Correct 4 ms 716 KB Output is correct
4 Correct 2 ms 716 KB Output is correct
5 Correct 3 ms 716 KB Output is correct
6 Correct 4 ms 728 KB Output is correct
7 Correct 3 ms 728 KB Output is correct
8 Correct 2 ms 728 KB Output is correct
9 Correct 4 ms 748 KB Output is correct
10 Correct 4 ms 748 KB Output is correct
11 Correct 3 ms 756 KB Output is correct
12 Correct 3 ms 756 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 756 KB Output is correct
2 Correct 2 ms 756 KB Output is correct
3 Correct 3 ms 756 KB Output is correct
4 Correct 878 ms 15788 KB Output is correct
5 Correct 688 ms 20004 KB Output is correct
6 Correct 968 ms 21764 KB Output is correct
7 Correct 1170 ms 26020 KB Output is correct
8 Correct 685 ms 26300 KB Output is correct
9 Correct 1125 ms 35008 KB Output is correct
10 Correct 977 ms 39328 KB Output is correct
11 Correct 3 ms 39328 KB Output is correct

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 39328 KB Output is correct
2 Correct 4 ms 39328 KB Output is correct
3 Correct 4 ms 39328 KB Output is correct
4 Correct 3 ms 39328 KB Output is correct
5 Correct 2 ms 39328 KB Output is correct
6 Correct 4 ms 39328 KB Output is correct
7 Correct 3 ms 39328 KB Output is correct
8 Correct 2 ms 39328 KB Output is correct
9 Correct 3 ms 39328 KB Output is correct
10 Correct 3 ms 39328 KB Output is correct
11 Correct 3 ms 39328 KB Output is correct
12 Correct 2021 ms 67660 KB Output is correct
13 Correct 4249 ms 67660 KB Output is correct
14 Correct 535 ms 67660 KB Output is correct
15 Correct 4933 ms 69660 KB Output is correct
16 Correct 1674 ms 92216 KB Output is correct
17 Correct 2105 ms 92216 KB Output is correct
18 Correct 4118 ms 102828 KB Output is correct
19 Correct 3570 ms 108368 KB Output is correct
20 Correct 3147 ms 112892 KB Output is correct
21 Correct 3 ms 112892 KB Output is correct

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 112892 KB Output is correct
2 Correct 3 ms 112892 KB Output is correct
3 Correct 4 ms 112892 KB Output is correct
4 Correct 2 ms 112892 KB Output is correct
5 Correct 2 ms 112892 KB Output is correct
6 Correct 4 ms 112892 KB Output is correct
7 Correct 3 ms 112892 KB Output is correct
8 Correct 3 ms 112892 KB Output is correct
9 Correct 4 ms 112892 KB Output is correct
10 Correct 3 ms 112892 KB Output is correct
11 Correct 3 ms 112892 KB Output is correct
12 Correct 1000 ms 112892 KB Output is correct
13 Correct 766 ms 112892 KB Output is correct
14 Correct 1052 ms 112892 KB Output is correct
15 Correct 1259 ms 112892 KB Output is correct
16 Correct 789 ms 112892 KB Output is correct
17 Correct 1230 ms 112892 KB Output is correct
18 Correct 1136 ms 112892 KB Output is correct
19 Correct 2073 ms 140972 KB Output is correct
20 Correct 4230 ms 140972 KB Output is correct
21 Correct 499 ms 140972 KB Output is correct
22 Correct 5207 ms 142992 KB Output is correct
23 Correct 1783 ms 165568 KB Output is correct
24 Correct 2033 ms 165568 KB Output is correct
25 Correct 4013 ms 176200 KB Output is correct
26 Correct 3405 ms 181688 KB Output is correct
27 Correct 3308 ms 186308 KB Output is correct
28 Execution timed out 10439 ms 257024 KB Time limit exceeded (wall clock)
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 257024 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -