oj.uz

Submission #1102624

# Submission time Handle Problem Language Result Execution time Memory
1102624 2024-10-18T13:19:11 Z ttamx Game (IOI13_game) C++17
10 / 100
 1280 ms 7960 KB 
#include "game.h"
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ll gcd2(ll X,ll Y){
    while(Y!=0)tie(X,Y)=make_pair(Y,X%Y);
    return X;
}

int n,m;

struct Treap{
    struct Node;
    using Ptr = Node*;
    struct Node{
        ll val,sum;
        int key,prio;
        Ptr l,r;
        Node(int i,ll v):val(v),sum(v),key(i),prio(rng()),l(),r(){}
    };
    Ptr root;
    Treap():root(){}
    ll get(Ptr t){
        return t?t->sum:0LL;
    }
    void pull(Ptr t){
        t->sum=gcd2(t->val,gcd2(get(t->l),get(t->r)));
    }
    void merge(Ptr &t,Ptr l,Ptr r){
        if(!l)return void(t=r);
        if(!r)return void(t=l);
        if(l->prio>r->prio)merge(l->r,l->r,r),t=l;
        else merge(r->l,l,r->l),t=r;
        pull(t);
    }
    void split(Ptr t,Ptr &l,Ptr &r,int key){
        if(!t)return void(l=r=t);
        if(t->key<=key)split(t->r,t->r,r,key),l=t;
        else split(t->l,l,t->l,key),r=t;
        pull(t);
    }
    Ptr get_right(Ptr t){
        while(t->r)t=t->r;
        return t;
    }
    void modify(int x,ll v){
        Ptr l,r;
        split(root,l,r,x);
        if(!l||get_right(l)->key!=x)merge(l,l,new Node(x,v));
        else get_right(l)->val=v;
        merge(root,l,r);
    }
    ll query(int x,int y){
        Ptr l,t,r;
        split(root,l,root,x-1);
        split(root,t,r,y);
        ll res=get(t);
        merge(root,l,t);
        merge(root,root,r);
        return res;
    }
};

struct SegTree2D{
    struct Node;
    using Ptr = Node*;
    struct Node{
        Treap tree;
        Ptr l,r;
        Node():tree(),l(),r(){}
    };
    Ptr root;
    SegTree2D():root(){}
    ll get(Ptr t,int x){
        return t?t->tree.query(x,x):0LL;
    }
    void modify(int l,int r,Ptr &t,int x,int y,ll v){
        if(!t)t=new Node();
        if(l<r){
            int m=(l+r)/2;
            if(x<=m)modify(l,m,t->l,x,y,v);
            else modify(m+1,r,t->r,x,y,v);
            v=gcd2(get(t->l,y),get(t->r,y));
        }
        t->tree.modify(y,v);
    }
    void modify(int x,int y,ll v){
        modify(0,n-1,root,x,y,v);
    }
    ll query(int l,int r,Ptr &t,int x,int y,int x2,int y2){
        if(y<l||r<x||!t)return 0LL;
        if(x<=l&&r<=y)return t->tree.query(x2,y2);
        int m=(l+r)/2;
        return gcd2(query(l,m,t->l,x,y,x2,y2),query(m+1,r,t->r,x,y,x2,y2));
    }
    ll query(int x,int y,int x2,int y2){
        return query(0,n-1,root,x,y,x2,y2);
    }
}seg;

void init(int R,int C){
    n=R,m=C;
}

void update(int P,int Q,ll K){
    seg.modify(P,Q,K);
}

ll calculate(int P,int Q,int U,int V){
    return seg.query(P,U,Q,V);
}

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 510 ms 6288 KB Output is correct
5 Correct 234 ms 6728 KB Output is correct
6 Incorrect 739 ms 3428 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 440 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 472 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 714 ms 7960 KB Output is correct
13 Incorrect 1280 ms 3144 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 508 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 503 ms 6436 KB Output is correct
13 Correct 236 ms 6728 KB Output is correct
14 Incorrect 755 ms 3400 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 552 ms 6472 KB Output is correct
13 Correct 257 ms 6680 KB Output is correct
14 Incorrect 729 ms 3496 KB Output isn't correct
15 Halted 0 ms 0 KB -