oj.uz

Submission #962983

# Submission time Handle Problem Language Result Execution time Memory
962983 2024-04-14T10:28:12 Z serkanrashid Game (IOI13_game) C++14
63 / 100
 1357 ms 256000 KB 
#include "game.h"
#include <bits/stdc++.h>

using namespace std;

struct Tnode
{
    long long a;
    Tnode *l, *r;
    Tnode()
    {
        a = 0;
        l = r = nullptr;
    }
};

struct Tree
{
    Tnode *A;
    Tree *L, *R;
    Tree()
    {
        A = nullptr;
        L = R = nullptr;
    }
};

Tree *Root = nullptr;
int r,c;

int Ql,Qr,ql,qr,Pos,pos;
long long val;

long long gcd3(long long a, long long b)
{
    while(a&&b)
    {
        if(a>b) a %= b;
        else b %= a;
    }
    return a+b;
}

long long merge1(Tnode *&t1, Tnode *&t2)
{
    if(t1==nullptr&&t2==nullptr) return 0;
    if(t1==nullptr) return t2->a;
    if(t2==nullptr) return t1->a;
    return gcd3(t1->a,t2->a);
}

void upd(Tnode *&t, int l, int r)
{
    if(t==nullptr) t = new Tnode();
    if(l==r)
    {
        t->a = val;
        //cout << l << " " << r << " " << (t->a) << "upd" << endl;
        return;
    }
    int mid = (l+r)/2;
    if(pos<=mid) upd(t->l,l,mid+0);
    else upd(t->r,mid+1,r);
    t->a = merge1(t->l,t->r);
    //cout << l << " " << r << " " << (t->a) << "upd" << endl;
}

Tnode *getA(Tree *&t)
{
    if(t==nullptr) return nullptr;
    return t->A;
}

long long geta(Tnode *&t)
{
    if(t==nullptr) return 0;
    return (t->a);
}

void Merge(Tnode *&t, Tnode *t1, Tnode *t2, int l, int r)
{
    if(t==nullptr) t = new Tnode();
    if(l==r)
    {
        t->a = gcd3(geta(t1),geta(t2));
        //cout << l << " " << r << " " << (t->a) << "merge" << endl;
        return;
    }
    int mid = (l+r)/2;
    if(pos<=mid)
    {
        if(t1!=nullptr) t1 = t1->l;
        if(t2!=nullptr) t2 = t2->l;
        Merge(t->l,t1,t2,l,mid+0);
    }
    else
    {
        if(t1!=nullptr) t1 = t1->r;
        if(t2!=nullptr) t2 = t2->r;
        Merge(t->r,t1,t2,mid+1,r);
    }
    t->a = gcd3(geta(t->l),geta(t->r));
    //cout << l << " " << r << " " << (t->a) << "merge" << endl;
}

void Upd(Tree *&t, int l, int r)
{
    if(t==nullptr) t = new Tree();
    if(l==r)
    {
        upd(t->A,0,c-1);
        return;
    }
    int mid = (l+r)/2;
    if(Pos<=mid) Upd(t->L,l,mid+0);
    else Upd(t->R,mid+1,r);
    //cout << "new Merge" << " " << l << " " << r << endl;
    Merge(t->A,getA(t->L),getA(t->R),0,c-1);
}

void update(int P, int Q, long long K)
{
    Pos = P;
    pos = Q;
    val = K;
    Upd(Root,0,r-1);
    //cout << ((Root->A)->a) << "after update" << endl;
}

long long query(Tnode *t, int l, int r)
{
    if(r<ql||qr<l||l>r||t==nullptr) return 0;
    if(ql<=l&&r<=qr) return t->a;
    int mid = (l+r)/2;
    long long ch1 = query(t->l,l,mid+0);
    long long ch2 = query(t->r,mid+1,r);
    return gcd3(ch1,ch2);
}

long long Query(Tree *t, int l, int r)
{
    if(r<Ql||Qr<l||l>r||t==nullptr) return 0;
    if(Ql<=l&&r<=Qr)
    {
        long long ch = query(t->A,0,c-1);
        return ch;
    }
    int mid = (l+r)/2;
    long long ch1 = Query(t->L,l,mid+0);
    long long ch2 = Query(t->R,mid+1,r);
    return gcd3(ch1,ch2);
}

long long calculate(int P, int Q, int U, int V)
{
    ql = Q;
    qr = V;
    ///
    Ql = P;
    Qr = U;
    long long ans = Query(Root,0,r-1);
    return ans;
}

void init(int R, int C)
{
    r = R;
    c = C;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 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 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 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 1 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 399 ms 12604 KB Output is correct
5 Correct 319 ms 13060 KB Output is correct
6 Correct 326 ms 9856 KB Output is correct
7 Correct 353 ms 9552 KB Output is correct
8 Correct 257 ms 6616 KB Output is correct
9 Correct 362 ms 9812 KB Output is correct
10 Correct 304 ms 9344 KB Output is correct
11 Correct 1 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 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 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 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 640 ms 15716 KB Output is correct
13 Correct 949 ms 6224 KB Output is correct
14 Correct 203 ms 1060 KB Output is correct
15 Correct 1151 ms 8792 KB Output is correct
16 Correct 141 ms 18308 KB Output is correct
17 Correct 556 ms 11552 KB Output is correct
18 Correct 982 ms 18540 KB Output is correct
19 Correct 791 ms 18840 KB Output is correct
20 Correct 728 ms 18176 KB Output is correct
21 Correct 1 ms 348 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 392 ms 12664 KB Output is correct
13 Correct 265 ms 13084 KB Output is correct
14 Correct 336 ms 9836 KB Output is correct
15 Correct 348 ms 9488 KB Output is correct
16 Correct 276 ms 6768 KB Output is correct
17 Correct 346 ms 9704 KB Output is correct
18 Correct 327 ms 9520 KB Output is correct
19 Correct 599 ms 15892 KB Output is correct
20 Correct 991 ms 6220 KB Output is correct
21 Correct 202 ms 852 KB Output is correct
22 Correct 1154 ms 8592 KB Output is correct
23 Correct 147 ms 18236 KB Output is correct
24 Correct 537 ms 11624 KB Output is correct
25 Correct 954 ms 18744 KB Output is correct
26 Correct 782 ms 18616 KB Output is correct
27 Correct 682 ms 18004 KB Output is correct
28 Correct 794 ms 251676 KB Output is correct
29 Runtime error 1357 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 1 ms 348 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 1 ms 344 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 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 389 ms 12628 KB Output is correct
13 Correct 273 ms 13016 KB Output is correct
14 Correct 335 ms 10156 KB Output is correct
15 Correct 396 ms 9616 KB Output is correct
16 Correct 246 ms 6648 KB Output is correct
17 Correct 369 ms 9732 KB Output is correct
18 Correct 348 ms 9536 KB Output is correct
19 Correct 586 ms 15808 KB Output is correct
20 Correct 1018 ms 6044 KB Output is correct
21 Correct 209 ms 844 KB Output is correct
22 Correct 1161 ms 8740 KB Output is correct
23 Correct 147 ms 18172 KB Output is correct
24 Correct 546 ms 11436 KB Output is correct
25 Correct 965 ms 19008 KB Output is correct
26 Correct 832 ms 18688 KB Output is correct
27 Correct 719 ms 18048 KB Output is correct
28 Correct 703 ms 251624 KB Output is correct
29 Runtime error 1291 ms 256000 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -