oj.uz

Submission #729906

# Submission time Handle Problem Language Result Execution time Memory
729906 2023-04-24T19:49:10 Z Rasoul006 Game (IOI13_game) C++17
37 / 100
 705 ms 25896 KB 
#include "game.h"

#include <bits/stdc++.h>

#define endl "\n"

#define F first

#define S second

#define pb push_back

#define all(x) x.begin() , x.end()

#define mm(dp , val) memset (dp , val , sizeof dp)

#define mid ((r+l)>>1)

#define lx (n<<1)

#define rx ((n<<1)|1)

#define low (i&(-i))

#define lb lower_bound

#define ub upper_bound

#define no void (cout << "NO" << endl)

#define one void (cout << "-1" << endl)

#define zer void (cout << "0" << endl)

#define yes void (cout << "YES" << endl)

typedef long long ll;

using namespace std;

const int logn = 26 ;

const int N = 1e6+5;

ll dx[] = {0 , 0 , 1 , -1};
ll dy[] = {1 , -1 , 0 , 0};

long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

ll n , m ;

struct seg_tree
{
    ll gcd[N] ;

    void build (ll n , ll l , ll r)
    {
        if (l == r)
        {
            gcd[n] = 0 ;
            return ;
        }

        build (lx , l , mid);
        build (rx , mid+1 , r);

        gcd[n] = gcd2(gcd[lx] , gcd[rx]) ;
    }

    void upd (ll n , ll l , ll r , ll i , ll v)
    {
        if (l == r)
        {
            gcd[n] = v ;
            return ;
        }

        if (i <= mid)
            upd(lx , l , mid , i , v) ;
        else
            upd(rx , mid+1 , r , i , v) ;

        gcd[n] = gcd2(gcd[lx] , gcd[rx]) ;
    }

    ll qry (ll n , ll l , ll r , ll x , ll y)
    {
        if (l > y || r < x)
            return 0  ;

        if (x <= l && r<=y)
            return gcd[n] ;

        ll le = qry(lx , l , mid , x , y) ;
        ll ri = qry(rx , mid+1 , r , x , y) ;

        return gcd2(le , ri) ;
    }
} tree[102] ;

ll get (ll x1 , ll y1 , ll x2 , ll y2)
{
    ll ret = 0 ;

    for (int i = x1 ; i<=x2 ; i++)
        ret = gcd2(ret , tree[i].qry (1 , 0 , m-1 , y1 , y2));

    return ret ;
}

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

void update(int P, int Q, long long K)
{
    tree[P].upd(1 , 0 , m-1 , Q , K) ;
}

long long calculate(int P, int Q, int U, int V) {

    return get(P , Q , U , V) ;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 980 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 1 ms 212 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 643 ms 20632 KB Output is correct
5 Correct 410 ms 20812 KB Output is correct
6 Correct 664 ms 21292 KB Output is correct
7 Correct 630 ms 20972 KB Output is correct
8 Correct 476 ms 19652 KB Output is correct
9 Correct 598 ms 21016 KB Output is correct
10 Correct 598 ms 20580 KB Output is correct
11 Correct 1 ms 212 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 980 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Runtime error 11 ms 340 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 980 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 705 ms 20532 KB Output is correct
13 Correct 402 ms 24800 KB Output is correct
14 Correct 652 ms 25884 KB Output is correct
15 Correct 700 ms 25604 KB Output is correct
16 Correct 530 ms 23944 KB Output is correct
17 Correct 669 ms 25592 KB Output is correct
18 Correct 582 ms 25216 KB Output is correct
19 Runtime error 11 ms 340 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 980 KB Output is correct
3 Correct 1 ms 980 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 980 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 681 ms 20568 KB Output is correct
13 Correct 456 ms 24780 KB Output is correct
14 Correct 590 ms 25896 KB Output is correct
15 Correct 593 ms 25624 KB Output is correct
16 Correct 560 ms 23916 KB Output is correct
17 Correct 674 ms 25672 KB Output is correct
18 Correct 560 ms 25252 KB Output is correct
19 Runtime error 11 ms 320 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -