oj.uz

Submission #65447

# Submission time Handle Problem Language Result Execution time Memory
65447 2018-08-07T15:52:37 Z boook Game (IOI13_game) C++14
63 / 100
 4977 ms 201372 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){
    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 2 ms 248 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 2 ms 520 KB Output is correct
4 Correct 2 ms 520 KB Output is correct
5 Correct 2 ms 520 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 2 ms 644 KB Output is correct
10 Correct 3 ms 644 KB Output is correct
11 Correct 3 ms 644 KB Output is correct
12 Correct 2 ms 644 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 644 KB Output is correct
2 Correct 3 ms 644 KB Output is correct
3 Correct 3 ms 644 KB Output is correct
4 Correct 915 ms 11324 KB Output is correct
5 Correct 716 ms 11520 KB Output is correct
6 Correct 822 ms 11520 KB Output is correct
7 Correct 1072 ms 11520 KB Output is correct
8 Correct 720 ms 11520 KB Output is correct
9 Correct 989 ms 11520 KB Output is correct
10 Correct 1010 ms 11520 KB Output is correct
11 Correct 2 ms 11520 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11520 KB Output is correct
2 Correct 3 ms 11520 KB Output is correct
3 Correct 3 ms 11520 KB Output is correct
4 Correct 4 ms 11520 KB Output is correct
5 Correct 3 ms 11520 KB Output is correct
6 Correct 4 ms 11520 KB Output is correct
7 Correct 3 ms 11520 KB Output is correct
8 Correct 2 ms 11520 KB Output is correct
9 Correct 2 ms 11520 KB Output is correct
10 Correct 2 ms 11520 KB Output is correct
11 Correct 3 ms 11520 KB Output is correct
12 Correct 2098 ms 25772 KB Output is correct
13 Correct 4074 ms 25772 KB Output is correct
14 Correct 467 ms 25772 KB Output is correct
15 Correct 4977 ms 25772 KB Output is correct
16 Correct 1619 ms 29508 KB Output is correct
17 Correct 1931 ms 29508 KB Output is correct
18 Correct 3613 ms 29960 KB Output is correct
19 Correct 3066 ms 30036 KB Output is correct
20 Correct 2772 ms 30036 KB Output is correct
21 Correct 3 ms 30036 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 30036 KB Output is correct
2 Correct 4 ms 30036 KB Output is correct
3 Correct 3 ms 30036 KB Output is correct
4 Correct 2 ms 30036 KB Output is correct
5 Correct 2 ms 30036 KB Output is correct
6 Correct 2 ms 30036 KB Output is correct
7 Correct 3 ms 30036 KB Output is correct
8 Correct 3 ms 30036 KB Output is correct
9 Correct 3 ms 30036 KB Output is correct
10 Correct 3 ms 30036 KB Output is correct
11 Correct 3 ms 30036 KB Output is correct
12 Correct 871 ms 30036 KB Output is correct
13 Correct 784 ms 30036 KB Output is correct
14 Correct 964 ms 30036 KB Output is correct
15 Correct 1202 ms 30036 KB Output is correct
16 Correct 650 ms 30036 KB Output is correct
17 Correct 1151 ms 30036 KB Output is correct
18 Correct 800 ms 30036 KB Output is correct
19 Correct 1929 ms 30036 KB Output is correct
20 Correct 4057 ms 30036 KB Output is correct
21 Correct 493 ms 30036 KB Output is correct
22 Correct 4564 ms 30036 KB Output is correct
23 Correct 1679 ms 30036 KB Output is correct
24 Correct 2220 ms 30036 KB Output is correct
25 Correct 3840 ms 30744 KB Output is correct
26 Correct 3141 ms 35452 KB Output is correct
27 Correct 2979 ms 40116 KB Output is correct
28 Runtime error 400 ms 158824 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 Correct 3 ms 158824 KB Output is correct
2 Correct 4 ms 158824 KB Output is correct
3 Correct 5 ms 158824 KB Output is correct
4 Correct 3 ms 158824 KB Output is correct
5 Correct 2 ms 158824 KB Output is correct
6 Correct 3 ms 158824 KB Output is correct
7 Correct 2 ms 158824 KB Output is correct
8 Correct 3 ms 158824 KB Output is correct
9 Correct 4 ms 158824 KB Output is correct
10 Correct 3 ms 158824 KB Output is correct
11 Correct 3 ms 158824 KB Output is correct
12 Correct 994 ms 158824 KB Output is correct
13 Correct 645 ms 158824 KB Output is correct
14 Correct 939 ms 158824 KB Output is correct
15 Correct 1136 ms 158824 KB Output is correct
16 Correct 674 ms 158824 KB Output is correct
17 Correct 1031 ms 158824 KB Output is correct
18 Correct 909 ms 158824 KB Output is correct
19 Correct 2128 ms 158824 KB Output is correct
20 Correct 4527 ms 158824 KB Output is correct
21 Correct 499 ms 158824 KB Output is correct
22 Correct 4358 ms 158824 KB Output is correct
23 Correct 1720 ms 158824 KB Output is correct
24 Correct 2129 ms 158824 KB Output is correct
25 Correct 3633 ms 158824 KB Output is correct
26 Correct 2988 ms 158824 KB Output is correct
27 Correct 3275 ms 158824 KB Output is correct
28 Runtime error 406 ms 201372 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -