oj.uz

Submission #749854

# Submission time Handle Problem Language Result Execution time Memory
749854 2023-05-28T18:46:13 Z grogu Game (IOI13_game) C++14
80 / 100
 4078 ms 207104 KB 
#include "game.h"
#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include <bits/stdc++.h>
#define ld long long
#define ll int
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define eb emplace_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}
#define si(a) (ll)(a.size())
using namespace std;

ld gcd(ld x,ld y){
    if(y>x) swap(x,y);
    if(y==0) return x;
    return gcd(y,x%y);
}
const ll maxx = 10000005;
const ld mc = 1000000000;
ll t[maxx],ls[maxx],rs[maxx],tsz = 0,root = 0;
ld t2[maxx];
ld get2(ll v,ll tl,ll tr,ll l,ll r){
    if(!v) return 0;
    if(tl>tr||tl>r||l>r||l>tr) return 0;
    if(tl>=l&&tr<=r) return t2[v];
    ll mid = (tl+tr)/2;
    return gcd(get2(ls[v],tl,mid,l,r),get2(rs[v],mid+1,tr,l,r));
}
ld get(ll v,ll tl,ll tr,ll l,ll r,ll x,ll y){
    if(!v) return 0;
    if(tl>tr||tl>r||l>tr||l>r) return 0;
    if(tl>=l&&tr<=r) return get2(t[v],1,mc,x,y);
    ll mid = (tl+tr)/2;
    return gcd(get(ls[v],tl,mid,l,r,x,y),get(rs[v],mid+1,tr,l,r,x,y));
}
void upd2(ll &v,ll tl,ll tr,ll i,ld x){
    if(!v) v = ++tsz;
    if(tl==tr){t2[v] = x;return;}
    ll mid = (tl+tr)/2;
    if(i<=mid) upd2(ls[v],tl,mid,i,x);
    else upd2(rs[v],mid+1,tr,i,x);
    t2[v] = gcd(t2[ls[v]],t2[rs[v]]);
}
void upd(ll &v,ll tl,ll tr,ll x,ll y,ld val){
    if(!v) v = ++tsz;
    upd2(t[v],1,mc,y,gcd(val,gcd(get(root,1,mc,tl,x-1,y,y),get(root,1,mc,x+1,tr,y,y))));
    if(tl==tr) return;
    ll mid = (tl+tr)/2;
    if(x<=mid) upd(ls[v],tl,mid,x,y,val);
    else upd(rs[v],mid+1,tr,x,y,val);
}
void init(int R, int C) {

}

void update(int P, int Q, long long K) {
    P++;
    Q++;
    upd(root,1,mc,P,Q,K);
}

long long calculate(int P, int Q, int U, int V) {
    P++;
    Q++;
    U++;
    V++;
    if(P>U) swap(U,P);
    if(Q>V) swap(Q,V);
    return get(root,1,mc,P,U,Q,V);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 11 ms 468 KB Output is correct
3 Correct 8 ms 468 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 8 ms 504 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 10 ms 468 KB Output is correct
10 Correct 3 ms 340 KB Output is correct
11 Correct 3 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1365 ms 27292 KB Output is correct
5 Correct 1030 ms 27480 KB Output is correct
6 Correct 1210 ms 24472 KB Output is correct
7 Correct 1247 ms 24172 KB Output is correct
8 Correct 731 ms 15320 KB Output is correct
9 Correct 1253 ms 24464 KB Output is correct
10 Correct 1244 ms 24004 KB Output is correct
11 Correct 1 ms 340 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 11 ms 524 KB Output is correct
3 Correct 12 ms 468 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 11 ms 468 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 6 ms 528 KB Output is correct
10 Correct 3 ms 340 KB Output is correct
11 Correct 3 ms 340 KB Output is correct
12 Correct 2282 ms 12548 KB Output is correct
13 Correct 2678 ms 5920 KB Output is correct
14 Correct 1290 ms 1024 KB Output is correct
15 Correct 2835 ms 8916 KB Output is correct
16 Correct 1550 ms 14456 KB Output is correct
17 Correct 1616 ms 10652 KB Output is correct
18 Correct 2554 ms 14664 KB Output is correct
19 Correct 2369 ms 14876 KB Output is correct
20 Correct 2229 ms 14336 KB Output is correct
21 Correct 0 ms 340 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 8 ms 548 KB Output is correct
3 Correct 9 ms 440 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 7 ms 496 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 6 ms 548 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 3 ms 340 KB Output is correct
12 Correct 1148 ms 27308 KB Output is correct
13 Correct 1046 ms 27464 KB Output is correct
14 Correct 1154 ms 24364 KB Output is correct
15 Correct 1177 ms 24240 KB Output is correct
16 Correct 711 ms 15416 KB Output is correct
17 Correct 1196 ms 24340 KB Output is correct
18 Correct 1204 ms 23924 KB Output is correct
19 Correct 2137 ms 12548 KB Output is correct
20 Correct 2479 ms 5880 KB Output is correct
21 Correct 1134 ms 1096 KB Output is correct
22 Correct 2644 ms 8768 KB Output is correct
23 Correct 1416 ms 14504 KB Output is correct
24 Correct 1486 ms 10876 KB Output is correct
25 Correct 2571 ms 14736 KB Output is correct
26 Correct 2369 ms 15004 KB Output is correct
27 Correct 2268 ms 14288 KB Output is correct
28 Correct 800 ms 161352 KB Output is correct
29 Correct 1808 ms 185932 KB Output is correct
30 Correct 4074 ms 130472 KB Output is correct
31 Correct 3845 ms 101284 KB Output is correct
32 Correct 932 ms 10336 KB Output is correct
33 Correct 1033 ms 11952 KB Output is correct
34 Correct 560 ms 179656 KB Output is correct
35 Correct 1423 ms 97652 KB Output is correct
36 Correct 2660 ms 183772 KB Output is correct
37 Correct 2101 ms 184080 KB Output is correct
38 Correct 2058 ms 183260 KB Output is correct
39 Correct 1766 ms 143436 KB Output is correct
40 Correct 1 ms 340 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 7 ms 468 KB Output is correct
3 Correct 8 ms 468 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 8 ms 536 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 6 ms 468 KB Output is correct
10 Correct 3 ms 340 KB Output is correct
11 Correct 3 ms 340 KB Output is correct
12 Correct 1136 ms 27264 KB Output is correct
13 Correct 996 ms 27576 KB Output is correct
14 Correct 1141 ms 24464 KB Output is correct
15 Correct 1182 ms 24196 KB Output is correct
16 Correct 720 ms 15440 KB Output is correct
17 Correct 1207 ms 24320 KB Output is correct
18 Correct 1163 ms 24116 KB Output is correct
19 Correct 2045 ms 12552 KB Output is correct
20 Correct 2362 ms 5844 KB Output is correct
21 Correct 1118 ms 1104 KB Output is correct
22 Correct 2671 ms 8840 KB Output is correct
23 Correct 1419 ms 14468 KB Output is correct
24 Correct 1453 ms 10888 KB Output is correct
25 Correct 2553 ms 14944 KB Output is correct
26 Correct 2334 ms 14948 KB Output is correct
27 Correct 2273 ms 14356 KB Output is correct
28 Correct 785 ms 161404 KB Output is correct
29 Correct 1776 ms 185888 KB Output is correct
30 Correct 4078 ms 130688 KB Output is correct
31 Correct 3797 ms 101444 KB Output is correct
32 Correct 965 ms 10444 KB Output is correct
33 Correct 1008 ms 11756 KB Output is correct
34 Correct 562 ms 179652 KB Output is correct
35 Correct 1284 ms 97656 KB Output is correct
36 Correct 2526 ms 183804 KB Output is correct
37 Correct 2099 ms 183880 KB Output is correct
38 Correct 2076 ms 183368 KB Output is correct
39 Incorrect 1732 ms 207104 KB Output isn't correct
40 Halted 0 ms 0 KB -