oj.uz

Submission #65449

# Submission time Handle Problem Language Result Execution time Memory
65449 2018-08-07T15:55:21 Z boook Game (IOI13_game) C++14
63 / 100
 4847 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 23000
#define INF 0x3f3f3f3f
#define mid (l + (r - l) / 2)

long long n , m;
long long sum[MAX * 360];
int ls[MAX * 360] , rs[MAX * 360] , 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){
    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) {
    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:77:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 584 KB Output is correct
3 Correct 4 ms 584 KB Output is correct
4 Correct 3 ms 584 KB Output is correct
5 Correct 3 ms 600 KB Output is correct
6 Correct 3 ms 652 KB Output is correct
7 Correct 3 ms 652 KB Output is correct
8 Correct 4 ms 652 KB Output is correct
9 Correct 3 ms 676 KB Output is correct
10 Correct 4 ms 676 KB Output is correct
11 Correct 3 ms 676 KB Output is correct
12 Correct 2 ms 676 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 676 KB Output is correct
2 Correct 3 ms 676 KB Output is correct
3 Correct 3 ms 724 KB Output is correct
4 Correct 829 ms 11484 KB Output is correct
5 Correct 652 ms 11488 KB Output is correct
6 Correct 1020 ms 11488 KB Output is correct
7 Correct 1234 ms 11488 KB Output is correct
8 Correct 679 ms 11488 KB Output is correct
9 Correct 1193 ms 11488 KB Output is correct
10 Correct 920 ms 11488 KB Output is correct
11 Correct 3 ms 11488 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11488 KB Output is correct
2 Correct 3 ms 11488 KB Output is correct
3 Correct 3 ms 11488 KB Output is correct
4 Correct 4 ms 11488 KB Output is correct
5 Correct 3 ms 11488 KB Output is correct
6 Correct 3 ms 11488 KB Output is correct
7 Correct 3 ms 11488 KB Output is correct
8 Correct 2 ms 11488 KB Output is correct
9 Correct 3 ms 11488 KB Output is correct
10 Correct 3 ms 11488 KB Output is correct
11 Correct 3 ms 11488 KB Output is correct
12 Correct 1970 ms 27204 KB Output is correct
13 Correct 3920 ms 27204 KB Output is correct
14 Correct 465 ms 27204 KB Output is correct
15 Correct 4771 ms 31964 KB Output is correct
16 Correct 1711 ms 48440 KB Output is correct
17 Correct 2036 ms 48440 KB Output is correct
18 Correct 4043 ms 59000 KB Output is correct
19 Correct 3234 ms 64408 KB Output is correct
20 Correct 3032 ms 69028 KB Output is correct
21 Correct 3 ms 69028 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 69028 KB Output is correct
2 Correct 3 ms 69028 KB Output is correct
3 Correct 4 ms 69028 KB Output is correct
4 Correct 3 ms 69028 KB Output is correct
5 Correct 3 ms 69028 KB Output is correct
6 Correct 6 ms 69028 KB Output is correct
7 Correct 2 ms 69028 KB Output is correct
8 Correct 3 ms 69028 KB Output is correct
9 Correct 3 ms 69028 KB Output is correct
10 Correct 4 ms 69028 KB Output is correct
11 Correct 3 ms 69028 KB Output is correct
12 Correct 850 ms 69028 KB Output is correct
13 Correct 832 ms 69028 KB Output is correct
14 Correct 962 ms 69028 KB Output is correct
15 Correct 1097 ms 69028 KB Output is correct
16 Correct 701 ms 69028 KB Output is correct
17 Correct 1025 ms 69028 KB Output is correct
18 Correct 947 ms 69028 KB Output is correct
19 Correct 1911 ms 69028 KB Output is correct
20 Correct 4287 ms 69028 KB Output is correct
21 Correct 514 ms 69028 KB Output is correct
22 Correct 4847 ms 71340 KB Output is correct
23 Correct 1602 ms 87884 KB Output is correct
24 Correct 2040 ms 87884 KB Output is correct
25 Correct 3508 ms 98304 KB Output is correct
26 Correct 3092 ms 98508 KB Output is correct
27 Correct 2885 ms 98508 KB Output is correct
28 Runtime error 714 ms 257024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 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 -