oj.uz

Submission #65445

# Submission time Handle Problem Language Result Execution time Memory
65445 2018-08-07T15:50:44 Z boook Game (IOI13_game) C++14
37 / 100
 1239 ms 31788 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 * 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -