oj.uz

Submission #749860

# Submission time Handle Problem Language Result Execution time Memory
749860 2023-05-28T19:05:35 Z grogu Game (IOI13_game) C++14
80 / 100
 3905 ms 256000 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 long long
#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 = 30000005;
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;
    if(tl==tr){upd2(t[v],1,mc,y,val);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);
    upd2(t[v],1,mc,y,gcd(get2(t[ls[v]],1,mc,y,y),get2(t[rs[v]],1,mc,y,y)));
}
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 7 ms 596 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 1 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 1 ms 340 KB Output is correct
4 Correct 846 ms 38752 KB Output is correct
5 Correct 752 ms 38916 KB Output is correct
6 Correct 924 ms 35948 KB Output is correct
7 Correct 899 ms 35868 KB Output is correct
8 Correct 595 ms 22116 KB Output is correct
9 Correct 904 ms 36164 KB Output is correct
10 Correct 901 ms 35452 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 1 ms 340 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 4 ms 596 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 1305 ms 17016 KB Output is correct
13 Correct 1654 ms 8848 KB Output is correct
14 Correct 616 ms 1136 KB Output is correct
15 Correct 1862 ms 13428 KB Output is correct
16 Correct 652 ms 21760 KB Output is correct
17 Correct 1188 ms 16000 KB Output is correct
18 Correct 1949 ms 22056 KB Output is correct
19 Correct 1786 ms 22280 KB Output is correct
20 Correct 1747 ms 21552 KB Output is correct
21 Correct 1 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 3 ms 596 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 3 ms 596 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 808 ms 38856 KB Output is correct
13 Correct 657 ms 38984 KB Output is correct
14 Correct 807 ms 36048 KB Output is correct
15 Correct 912 ms 35772 KB Output is correct
16 Correct 553 ms 22140 KB Output is correct
17 Correct 858 ms 36128 KB Output is correct
18 Correct 900 ms 35524 KB Output is correct
19 Correct 1257 ms 17084 KB Output is correct
20 Correct 1604 ms 8772 KB Output is correct
21 Correct 583 ms 1228 KB Output is correct
22 Correct 1829 ms 13460 KB Output is correct
23 Correct 651 ms 21636 KB Output is correct
24 Correct 1191 ms 16028 KB Output is correct
25 Correct 1899 ms 22040 KB Output is correct
26 Correct 1785 ms 22364 KB Output is correct
27 Correct 1689 ms 21556 KB Output is correct
28 Correct 790 ms 230300 KB Output is correct
29 Correct 1840 ms 251544 KB Output is correct
30 Correct 3905 ms 174736 KB Output is correct
31 Correct 3667 ms 133216 KB Output is correct
32 Correct 512 ms 1204 KB Output is correct
33 Correct 642 ms 3584 KB Output is correct
34 Correct 515 ms 248576 KB Output is correct
35 Correct 1307 ms 125848 KB Output is correct
36 Correct 2559 ms 249132 KB Output is correct
37 Correct 2135 ms 249244 KB Output is correct
38 Correct 2086 ms 248732 KB Output is correct
39 Correct 1746 ms 191128 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 3 ms 632 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 814 ms 38872 KB Output is correct
13 Correct 660 ms 39084 KB Output is correct
14 Correct 857 ms 36100 KB Output is correct
15 Correct 868 ms 35708 KB Output is correct
16 Correct 572 ms 22272 KB Output is correct
17 Correct 859 ms 36108 KB Output is correct
18 Correct 830 ms 35456 KB Output is correct
19 Correct 1276 ms 16856 KB Output is correct
20 Correct 1622 ms 8640 KB Output is correct
21 Correct 587 ms 1184 KB Output is correct
22 Correct 1839 ms 13264 KB Output is correct
23 Correct 671 ms 21812 KB Output is correct
24 Correct 1179 ms 16132 KB Output is correct
25 Correct 1946 ms 21964 KB Output is correct
26 Correct 1707 ms 22156 KB Output is correct
27 Correct 1695 ms 21512 KB Output is correct
28 Correct 747 ms 230536 KB Output is correct
29 Correct 1762 ms 251496 KB Output is correct
30 Correct 3878 ms 174636 KB Output is correct
31 Correct 3619 ms 133416 KB Output is correct
32 Correct 511 ms 1228 KB Output is correct
33 Correct 649 ms 3540 KB Output is correct
34 Correct 525 ms 248684 KB Output is correct
35 Correct 1325 ms 125600 KB Output is correct
36 Correct 2610 ms 249000 KB Output is correct
37 Correct 2201 ms 249232 KB Output is correct
38 Correct 2125 ms 248880 KB Output is correct
39 Runtime error 506 ms 256000 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -