답안 #65445 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
65445	2018-08-07T15:50:44 Z	boook	게임 (IOI13_game)	C++14	37 / 100	1239 ms	31788 KB

game

#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 23000
#define INF 0x3f3f3f3f
#define mid (l + (r - l) / 2)

long long n , m;
long long sum[MAX * 400];
int ls[MAX * 400] , rs[MAX * 400] , 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	248 KB	Output is correct
2	Correct	3 ms	612 KB	Output is correct
3	Correct	3 ms	612 KB	Output is correct
4	Correct	3 ms	612 KB	Output is correct
5	Correct	3 ms	612 KB	Output is correct
6	Correct	4 ms	656 KB	Output is correct
7	Correct	4 ms	656 KB	Output is correct
8	Correct	3 ms	656 KB	Output is correct
9	Correct	3 ms	688 KB	Output is correct
10	Correct	3 ms	688 KB	Output is correct
11	Correct	2 ms	688 KB	Output is correct
12	Correct	2 ms	688 KB	Output is correct

Subtask #2
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	688 KB	Output is correct
2	Correct	3 ms	688 KB	Output is correct
3	Correct	3 ms	688 KB	Output is correct
4	Correct	985 ms	11400 KB	Output is correct
5	Correct	711 ms	11508 KB	Output is correct
6	Correct	1101 ms	11508 KB	Output is correct
7	Correct	1179 ms	11508 KB	Output is correct
8	Correct	656 ms	11508 KB	Output is correct
9	Correct	1118 ms	11508 KB	Output is correct
10	Correct	1025 ms	11508 KB	Output is correct
11	Correct	4 ms	11508 KB	Output is correct

Subtask #3
0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	11508 KB	Output is correct
2	Correct	3 ms	11508 KB	Output is correct
3	Correct	4 ms	11508 KB	Output is correct
4	Correct	3 ms	11508 KB	Output is correct
5	Correct	3 ms	11508 KB	Output is correct
6	Correct	4 ms	11508 KB	Output is correct
7	Correct	2 ms	11508 KB	Output is correct
8	Correct	2 ms	11508 KB	Output is correct
9	Correct	3 ms	11508 KB	Output is correct
10	Correct	4 ms	11508 KB	Output is correct
11	Correct	3 ms	11508 KB	Output is correct
12	Runtime error	996 ms	31788 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
13	Halted	0 ms	0 KB	-

Subtask #4
0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	31788 KB	Output is correct
2	Correct	4 ms	31788 KB	Output is correct
3	Correct	3 ms	31788 KB	Output is correct
4	Correct	2 ms	31788 KB	Output is correct
5	Correct	3 ms	31788 KB	Output is correct
6	Correct	4 ms	31788 KB	Output is correct
7	Correct	2 ms	31788 KB	Output is correct
8	Correct	4 ms	31788 KB	Output is correct
9	Correct	4 ms	31788 KB	Output is correct
10	Correct	3 ms	31788 KB	Output is correct
11	Correct	2 ms	31788 KB	Output is correct
12	Correct	987 ms	31788 KB	Output is correct
13	Correct	793 ms	31788 KB	Output is correct
14	Correct	994 ms	31788 KB	Output is correct
15	Correct	1239 ms	31788 KB	Output is correct
16	Correct	705 ms	31788 KB	Output is correct
17	Correct	1202 ms	31788 KB	Output is correct
18	Correct	969 ms	31788 KB	Output is correct
19	Runtime error	1159 ms	31788 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
20	Halted	0 ms	0 KB	-

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	31788 KB	Output is correct
2	Correct	4 ms	31788 KB	Output is correct
3	Correct	4 ms	31788 KB	Output is correct
4	Correct	3 ms	31788 KB	Output is correct
5	Correct	2 ms	31788 KB	Output is correct
6	Correct	4 ms	31788 KB	Output is correct
7	Correct	2 ms	31788 KB	Output is correct
8	Correct	3 ms	31788 KB	Output is correct
9	Correct	4 ms	31788 KB	Output is correct
10	Correct	4 ms	31788 KB	Output is correct
11	Correct	3 ms	31788 KB	Output is correct
12	Correct	897 ms	31788 KB	Output is correct
13	Correct	654 ms	31788 KB	Output is correct
14	Correct	1026 ms	31788 KB	Output is correct
15	Correct	1183 ms	31788 KB	Output is correct
16	Correct	590 ms	31788 KB	Output is correct
17	Correct	985 ms	31788 KB	Output is correct
18	Correct	1078 ms	31788 KB	Output is correct
19	Runtime error	1008 ms	31788 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
20	Halted	0 ms	0 KB	-

답안 #65445

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 27.0 / 27.0

Subtask #3 0 / 26.0

Subtask #4 0 / 17.0

Subtask #5 0 / 20.0

Subtask #1
10.0 / 10.0

Subtask #2
27.0 / 27.0

Subtask #3
0 / 26.0

Subtask #4
0 / 17.0

Subtask #5
0 / 20.0