oj.uz

Submission #65444

# Submission time Handle Problem Language Result Execution time Memory
65444 2018-08-07T15:49:09 Z boook Game (IOI13_game) C++14
37 / 100
 1251 ms 128048 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 * 200];
int ls[MAX * 200] , rs[MAX * 200] , 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 484 KB Output is correct
3 Correct 3 ms 520 KB Output is correct
4 Correct 2 ms 520 KB Output is correct
5 Correct 3 ms 520 KB Output is correct
6 Correct 3 ms 608 KB Output is correct
7 Correct 3 ms 688 KB Output is correct
8 Correct 3 ms 688 KB Output is correct
9 Correct 3 ms 728 KB Output is correct
10 Correct 3 ms 728 KB Output is correct
11 Correct 4 ms 728 KB Output is correct
12 Correct 4 ms 728 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 728 KB Output is correct
2 Correct 3 ms 728 KB Output is correct
3 Correct 4 ms 728 KB Output is correct
4 Correct 951 ms 12628 KB Output is correct
5 Correct 838 ms 16964 KB Output is correct
6 Correct 1057 ms 18364 KB Output is correct
7 Correct 1101 ms 22648 KB Output is correct
8 Correct 604 ms 24700 KB Output is correct
9 Correct 1116 ms 31728 KB Output is correct
10 Correct 938 ms 36084 KB Output is correct
11 Correct 3 ms 36084 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 36084 KB Output is correct
2 Correct 4 ms 36084 KB Output is correct
3 Correct 4 ms 36084 KB Output is correct
4 Correct 3 ms 36084 KB Output is correct
5 Correct 3 ms 36084 KB Output is correct
6 Correct 4 ms 36084 KB Output is correct
7 Correct 2 ms 36084 KB Output is correct
8 Correct 2 ms 36084 KB Output is correct
9 Correct 4 ms 36084 KB Output is correct
10 Correct 2 ms 36084 KB Output is correct
11 Correct 3 ms 36084 KB Output is correct
12 Runtime error 1251 ms 61660 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 3 ms 61660 KB Output is correct
2 Correct 3 ms 61660 KB Output is correct
3 Correct 3 ms 61660 KB Output is correct
4 Correct 2 ms 61660 KB Output is correct
5 Correct 3 ms 61660 KB Output is correct
6 Correct 3 ms 61660 KB Output is correct
7 Correct 2 ms 61660 KB Output is correct
8 Correct 3 ms 61660 KB Output is correct
9 Correct 4 ms 61660 KB Output is correct
10 Correct 3 ms 61660 KB Output is correct
11 Correct 5 ms 61660 KB Output is correct
12 Correct 957 ms 61660 KB Output is correct
13 Correct 674 ms 64012 KB Output is correct
14 Correct 918 ms 65764 KB Output is correct
15 Correct 1060 ms 69964 KB Output is correct
16 Correct 604 ms 71732 KB Output is correct
17 Correct 1149 ms 78996 KB Output is correct
18 Correct 925 ms 83256 KB Output is correct
19 Runtime error 1112 ms 95468 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 95468 KB Output is correct
2 Correct 3 ms 95468 KB Output is correct
3 Correct 4 ms 95468 KB Output is correct
4 Correct 3 ms 95468 KB Output is correct
5 Correct 4 ms 95468 KB Output is correct
6 Correct 3 ms 95468 KB Output is correct
7 Correct 3 ms 95468 KB Output is correct
8 Correct 3 ms 95468 KB Output is correct
9 Correct 3 ms 95468 KB Output is correct
10 Correct 3 ms 95468 KB Output is correct
11 Correct 3 ms 95468 KB Output is correct
12 Correct 919 ms 95468 KB Output is correct
13 Correct 725 ms 96652 KB Output is correct
14 Correct 1054 ms 98028 KB Output is correct
15 Correct 1128 ms 102408 KB Output is correct
16 Correct 611 ms 104348 KB Output is correct
17 Correct 1044 ms 111472 KB Output is correct
18 Correct 918 ms 115672 KB Output is correct
19 Runtime error 1109 ms 128048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -