oj.uz

Submission #426105

# Submission time Handle Problem Language Result Execution time Memory
426105 2021-06-13T14:09:28 Z Bill_00 Game (IOI13_game) C++14
37 / 100
 13000 ms 196252 KB 
#include "game.h"
#include <bits/stdc++.h>
typedef long long ll;
const ll value=3000000000;
using namespace std;
ll x,y,k,x_,y_;
unordered_map<ll,ll>t;
long long gcd2(long long X, long long Y) {
    if(Y>X) swap(X,Y);
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}
void updateY(ll vx, ll lx, ll rx, ll vy, ll ly, ll ry) {
    if (ly == ry) {
        if (lx == rx){
            t[vx*value+vy] = k;
        }
        else{
            t[vx*value+vy] = gcd2(t[vx*2*value+vy],t[(vx*2+1)*value+vy]);
            // cout << t[vx*2*value+vy] << '\n';
        }
    } else {
        ll my = (ly + ry) / 2;
        if(my>=y) updateY(vx, lx, rx, vy*2, ly, my);
        else updateY(vx, lx, rx, vy*2+1, my+1, ry);
        t[vx*value+vy] = gcd2(t[vx*value+vy*2],t[vx*value+vy*2+1]);
    }
    // cout << t[vx*value+vy] << ' ' << lx << ' ' << rx << ' ' << ly << ' ' << ry << '\n';
}

void updateX(ll vx, ll lx, ll rx) {
    if (lx != rx) {
        ll mx = (lx + rx) / 2;
        if(mx>=x) updateX(vx*2, lx, mx);
       	else updateX(vx*2+1, mx+1, rx);
    }
    updateY(vx, lx, rx, 1, 0, 1000000000);
}
void init(int R, int C) {
    /* ... */
}
void update(int P, int Q, long long K) {
    x=P;
    y=Q;
    k=K;
   	updateX(1,0,1000000000);
}
ll queryY(ll idx,ll L,ll R,ll idy,ll l,ll r) {
    if(r<y || y_<l) return 0;
    if(y<=l && r<=y_){
    	return t[idx*value+idy];	
    } 
    ll m=l+r>>1;
    return gcd2(queryY(idx,L,R,idy*2,l,m),queryY(idx,L,R,idy*2+1,m+1,r));
}

ll queryX(ll id,ll l,ll r) {
   if(r<x || x_<l) return 0;
   if(x<=l && r<=x_) return queryY(id,l,r,1,0,1000000000);
   ll m=l+r>>1;
   return gcd2(queryX(id*2,l,m),queryX(id*2+1,m+1,r));
}
long long calculate(int P, int Q, int U, int V) {
    /* ... */
    x=P;
    y=Q;
    x_=U;
    y_=V;
    return queryX(1,0,1000000000);
}

Compilation message

game.cpp: In function 'll queryY(ll, ll, ll, ll, ll, ll)':
game.cpp:58:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |     ll m=l+r>>1;
      |          ~^~
game.cpp: In function 'll queryX(ll, ll, ll)':
game.cpp:65:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |    ll m=l+r>>1;
      |         ~^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 332 KB Output is correct
2 Correct 13 ms 1336 KB Output is correct
3 Correct 16 ms 1356 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 12 ms 1100 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 11 ms 1052 KB Output is correct
10 Correct 5 ms 844 KB Output is correct
11 Correct 6 ms 580 KB Output is correct
12 Correct 1 ms 332 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 6758 ms 116536 KB Output is correct
5 Correct 5074 ms 113464 KB Output is correct
6 Correct 7143 ms 167436 KB Output is correct
7 Correct 6876 ms 167060 KB Output is correct
8 Correct 4927 ms 114220 KB Output is correct
9 Correct 7529 ms 168772 KB Output is correct
10 Correct 7021 ms 167048 KB Output is correct
11 Correct 1 ms 324 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 332 KB Output is correct
2 Correct 13 ms 1440 KB Output is correct
3 Correct 13 ms 1384 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 12 ms 1060 KB Output is correct
7 Correct 1 ms 420 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 11 ms 1056 KB Output is correct
10 Correct 5 ms 844 KB Output is correct
11 Correct 6 ms 588 KB Output is correct
12 Correct 6997 ms 46452 KB Output is correct
13 Correct 5721 ms 23872 KB Output is correct
14 Correct 3651 ms 7060 KB Output is correct
15 Correct 7600 ms 32404 KB Output is correct
16 Correct 3481 ms 56204 KB Output is correct
17 Correct 11409 ms 185840 KB Output is correct
18 Execution timed out 13074 ms 194600 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 332 KB Output is correct
2 Correct 14 ms 1352 KB Output is correct
3 Correct 13 ms 1356 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 12 ms 1100 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 11 ms 972 KB Output is correct
10 Correct 5 ms 836 KB Output is correct
11 Correct 7 ms 700 KB Output is correct
12 Correct 6938 ms 116768 KB Output is correct
13 Correct 5189 ms 113560 KB Output is correct
14 Correct 7447 ms 167424 KB Output is correct
15 Correct 6889 ms 167136 KB Output is correct
16 Correct 4899 ms 114208 KB Output is correct
17 Correct 7031 ms 168824 KB Output is correct
18 Correct 6438 ms 167088 KB Output is correct
19 Correct 6773 ms 46460 KB Output is correct
20 Correct 5718 ms 23732 KB Output is correct
21 Correct 3783 ms 7172 KB Output is correct
22 Correct 7332 ms 32524 KB Output is correct
23 Correct 3485 ms 56028 KB Output is correct
24 Correct 11288 ms 185928 KB Output is correct
25 Execution timed out 13109 ms 196252 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 332 KB Output is correct
2 Correct 13 ms 1444 KB Output is correct
3 Correct 13 ms 1356 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 12 ms 1044 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 12 ms 972 KB Output is correct
10 Correct 5 ms 844 KB Output is correct
11 Correct 6 ms 588 KB Output is correct
12 Correct 6688 ms 116504 KB Output is correct
13 Correct 5203 ms 113528 KB Output is correct
14 Correct 7203 ms 167408 KB Output is correct
15 Correct 6739 ms 167092 KB Output is correct
16 Correct 4202 ms 114476 KB Output is correct
17 Correct 6278 ms 168964 KB Output is correct
18 Correct 7312 ms 167092 KB Output is correct
19 Correct 6898 ms 46676 KB Output is correct
20 Correct 5782 ms 23804 KB Output is correct
21 Correct 3665 ms 7172 KB Output is correct
22 Correct 7604 ms 32528 KB Output is correct
23 Correct 3349 ms 56216 KB Output is correct
24 Correct 10971 ms 185888 KB Output is correct
25 Execution timed out 13068 ms 191520 KB Time limit exceeded
26 Halted 0 ms 0 KB -