oj.uz

Submission #65459

# Submission time Handle Problem Language Result Execution time Memory
65459 2018-08-07T16:02:15 Z boook Game (IOI13_game) C++14
63 / 100
 4771 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 * 700];
int ls[MAX * 700] , rs[MAX * 700] , 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){
    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:76: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 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 2 ms 612 KB Output is correct
6 Correct 3 ms 716 KB Output is correct
7 Correct 3 ms 716 KB Output is correct
8 Correct 3 ms 716 KB Output is correct
9 Correct 3 ms 716 KB Output is correct
10 Correct 3 ms 716 KB Output is correct
11 Correct 3 ms 716 KB Output is correct
12 Correct 3 ms 716 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 716 KB Output is correct
2 Correct 3 ms 716 KB Output is correct
3 Correct 2 ms 716 KB Output is correct
4 Correct 1134 ms 11296 KB Output is correct
5 Correct 821 ms 11712 KB Output is correct
6 Correct 916 ms 11712 KB Output is correct
7 Correct 1086 ms 11712 KB Output is correct
8 Correct 626 ms 11712 KB Output is correct
9 Correct 1131 ms 11712 KB Output is correct
10 Correct 1107 ms 11712 KB Output is correct
11 Correct 3 ms 11712 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 11712 KB Output is correct
2 Correct 5 ms 11712 KB Output is correct
3 Correct 4 ms 11712 KB Output is correct
4 Correct 3 ms 11712 KB Output is correct
5 Correct 3 ms 11712 KB Output is correct
6 Correct 4 ms 11712 KB Output is correct
7 Correct 2 ms 11712 KB Output is correct
8 Correct 2 ms 11712 KB Output is correct
9 Correct 3 ms 11712 KB Output is correct
10 Correct 3 ms 11712 KB Output is correct
11 Correct 3 ms 11712 KB Output is correct
12 Correct 2135 ms 27236 KB Output is correct
13 Correct 4228 ms 27236 KB Output is correct
14 Correct 565 ms 27236 KB Output is correct
15 Correct 4771 ms 31872 KB Output is correct
16 Correct 1670 ms 48136 KB Output is correct
17 Correct 2008 ms 48136 KB Output is correct
18 Correct 3668 ms 58848 KB Output is correct
19 Correct 3359 ms 64288 KB Output is correct
20 Correct 3241 ms 68984 KB Output is correct
21 Correct 3 ms 68984 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 68984 KB Output is correct
2 Correct 3 ms 68984 KB Output is correct
3 Correct 4 ms 68984 KB Output is correct
4 Correct 2 ms 68984 KB Output is correct
5 Correct 2 ms 68984 KB Output is correct
6 Correct 4 ms 68984 KB Output is correct
7 Correct 3 ms 68984 KB Output is correct
8 Correct 3 ms 68984 KB Output is correct
9 Correct 3 ms 68984 KB Output is correct
10 Correct 5 ms 68984 KB Output is correct
11 Correct 3 ms 68984 KB Output is correct
12 Correct 819 ms 68984 KB Output is correct
13 Correct 693 ms 68984 KB Output is correct
14 Correct 803 ms 68984 KB Output is correct
15 Correct 1201 ms 68984 KB Output is correct
16 Correct 693 ms 68984 KB Output is correct
17 Correct 1248 ms 68984 KB Output is correct
18 Correct 1107 ms 68984 KB Output is correct
19 Correct 2229 ms 68984 KB Output is correct
20 Correct 3850 ms 68984 KB Output is correct
21 Correct 488 ms 68984 KB Output is correct
22 Correct 4503 ms 71152 KB Output is correct
23 Correct 1601 ms 87564 KB Output is correct
24 Correct 2037 ms 87564 KB Output is correct
25 Correct 3679 ms 98416 KB Output is correct
26 Correct 2904 ms 98416 KB Output is correct
27 Correct 2807 ms 98416 KB Output is correct
28 Runtime error 1772 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.
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 -