oj.uz

Submission #989574

# Submission time Handle Problem Language Result Execution time Memory
989574 2024-05-28T10:44:55 Z User0069 Game (IOI13_game) C++17
63 / 100
 1052 ms 256000 KB 
#include<bits/stdc++.h>
#include"game.h"
#define taskname "vcl"
#define el '\n'
#define fi first
#define sc second
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
//#define int ll
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
#define Faster ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int maxn=2e5+3;
const int mod=1e9+7;
const int INF=1e9+7;
long long n,q,a[maxn],boundr,boundc;
long long gcd(long long a,long long b)
{
    if(b==0) return a;
    return gcd(b,a%b);
}
struct segtreetree
{
    struct segtree
    {
        struct node
        {
            long long val;
            node *l,*r;
            node(long long val): val(val),l(NULL),r(NULL){};
        }*root;
        long long vall(node* x) {return x?x->val:0;}
        void update(node* kk,int cl,int cr,int pos,long long val)
        {
            if(cl==cr)
            {
                kk->val=val;
                return;
            }
            int mid=(cl+cr)/2;
            if(pos<=mid)
            {
                if(kk->l==NULL) kk->l=new node(0);
                update(kk->l,cl,mid,pos,val);
            }
            else
            {
                if(kk->r==NULL) kk->r=new node(0);
                update(kk->r,mid+1,cr,pos,val);
            }
            kk->val=gcd(vall(kk->l),vall(kk->r));
        }
        long long get(node* kk,int cl,int cr,int l,int r)
        {
            if(kk==NULL||cl>r||cr<l) return 0;
            if(cl>=l&&cr<=r) return kk->val;
            int mid=(cl+cr)/2;
            return gcd(get(kk->l,cl,mid,l,r),get(kk->r,mid+1,cr,l,r));
        }
        segtree *l, *r;
        segtree(): root(new node(0)), l(NULL), r(NULL) {};
    }*root;
    void update(segtree* kk,int cl,int cr,int r,int c,long long val)
    {
        if(cl==cr)
        {
            kk->update(kk->root,0,boundc,c,val);
            return;
        }
        int mid=(cl+cr)/2;
        if(r<=mid)
        {
            if(kk->l==NULL) kk->l=new segtree();
            update(kk->l,cl,mid,r,c,val);
        }
        else
        {
            if(kk->r==NULL) kk->r=new segtree();
            update(kk->r,mid+1,cr,r,c,val);
        }
        long long u=0;
        if(kk->l) u=kk->l->get(kk->l->root,0,boundc,c,c);
        long long v=0;
        if(kk->r) v=kk->r->get(kk->r->root,0,boundc,c,c);
        kk->update(kk->root,0,boundc,c,gcd(u,v));
    }
    long long get(segtree *kk,int cl,int cr,int u,int l,int d,int r)
    {
        if(kk==NULL||cl>d||cr<u) return 0;
        if(cl>=u&&cr<=d) return kk->get(kk->root,0,boundc,l,r);
        int mid=(cl+cr)/2;
        return gcd(get(kk->l,cl,mid,u,l,d,r),get(kk->r,mid+1,cr,u,l,d,r));
    }
    segtreetree(): root(new segtree()){};
}*root=new segtreetree();
void init(int R,int C)
{
    boundr=R-1;
    boundc=C-1;
}
void update(int P,int Q, long long k)
{
    root->update(root->root,0,boundr,P,Q,k);
}
long long calculate(int P,int Q,int U,int V)
{
    return root->get(root->root,0,boundr,P,Q,U,V);
}
//signed main()
//{
//    if (fopen(taskname".INP","r"))
//    {
//        freopen(taskname".INP","r",stdin);
//        freopen(taskname"1.OUT","w",stdout);
//    }
//    Faster
//    long long R,C,N;
//    cin>>R>>C>>N;
//    init(R,C);
//    while(N--)
//    {
//        long long t;
//        cin>>t;
//        if(t==1)
//        {
//            long long a,b,c;
//            cin>>a>>b>>c;
//            update(a,b,c);
//        }
//        else
//        {
//            long long a,b,c,d;
//            cin>>a>>b>>c>>d;
//            cout<<calculate(a,b,c,d)<<"\n";
//        }
//    }
////    cout<<calculate(2,0,2,0);
//}

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 305 ms 16964 KB Output is correct
5 Correct 188 ms 16980 KB Output is correct
6 Correct 269 ms 14416 KB Output is correct
7 Correct 306 ms 14244 KB Output is correct
8 Correct 211 ms 10836 KB Output is correct
9 Correct 289 ms 14420 KB Output is correct
10 Correct 270 ms 13860 KB Output is correct
11 Correct 0 ms 344 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 444 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 440 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 352 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 503 ms 20052 KB Output is correct
13 Correct 673 ms 10064 KB Output is correct
14 Correct 164 ms 5648 KB Output is correct
15 Correct 805 ms 13244 KB Output is correct
16 Correct 129 ms 22608 KB Output is correct
17 Correct 494 ms 16488 KB Output is correct
18 Correct 725 ms 23944 KB Output is correct
19 Correct 654 ms 24056 KB Output is correct
20 Correct 613 ms 23376 KB Output is correct
21 Correct 0 ms 348 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 360 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 292 ms 17064 KB Output is correct
13 Correct 199 ms 16976 KB Output is correct
14 Correct 277 ms 14672 KB Output is correct
15 Correct 305 ms 14160 KB Output is correct
16 Correct 207 ms 11088 KB Output is correct
17 Correct 292 ms 14492 KB Output is correct
18 Correct 251 ms 13828 KB Output is correct
19 Correct 445 ms 20048 KB Output is correct
20 Correct 717 ms 10200 KB Output is correct
21 Correct 162 ms 5716 KB Output is correct
22 Correct 779 ms 13216 KB Output is correct
23 Correct 123 ms 22352 KB Output is correct
24 Correct 490 ms 16388 KB Output is correct
25 Correct 722 ms 23916 KB Output is correct
26 Correct 664 ms 24144 KB Output is correct
27 Correct 601 ms 23376 KB Output is correct
28 Correct 546 ms 256000 KB Output is correct
29 Runtime error 992 ms 256000 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 288 ms 16936 KB Output is correct
13 Correct 216 ms 16980 KB Output is correct
14 Correct 267 ms 14420 KB Output is correct
15 Correct 290 ms 14160 KB Output is correct
16 Correct 206 ms 10832 KB Output is correct
17 Correct 288 ms 14416 KB Output is correct
18 Correct 247 ms 13904 KB Output is correct
19 Correct 443 ms 20048 KB Output is correct
20 Correct 665 ms 10068 KB Output is correct
21 Correct 155 ms 5708 KB Output is correct
22 Correct 778 ms 13100 KB Output is correct
23 Correct 126 ms 22612 KB Output is correct
24 Correct 490 ms 16468 KB Output is correct
25 Correct 736 ms 23960 KB Output is correct
26 Correct 620 ms 24064 KB Output is correct
27 Correct 585 ms 23468 KB Output is correct
28 Correct 548 ms 256000 KB Output is correct
29 Runtime error 1052 ms 256000 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -