oj.uz

Submission #1091128

# Submission time Handle Problem Language Result Execution time Memory
1091128 2024-09-19T22:08:03 Z AtinaR Game (IOI13_game) C++14
37 / 100
 818 ms 256000 KB 
#include <bits/stdc++.h>
#include "game.h"
using namespace std;
const int MAX=2010;
long long gcd(long long a, long long b)
{
    if(b==0)return a;
    return gcd(b,a%b);
}
long long n,m;
vector<vector<long long> > tree;
//long long tree[4*MAX][4*MAX];
void init(int R, int C)
{
    n=R,m=C;
    tree.resize(4*n+10, vector<long long>(4*m+10));
}
long long sumy(long long nodex, long long nodey, long long L, long long R, long long _left, long long _right)
{
    if(L>=_left && R<=_right)return tree[nodex][nodey];
    else if(L>_right || R<_left)return 0;
    long long mid=(L+R)/2;
    long long l=sumy(nodex,2*nodey,L,mid,_left,_right);
    long long r=sumy(nodex,2*nodey+1,mid+1,R,_left,_right);
    return gcd(l,r);
}
long long sumx(long long node, long long L, long long R, long long _leftx, long long _rightx, long long _lefty, long long _righty)
{
    if(L>=_leftx && R<=_rightx)
    {
        return sumy(node,1,0,m-1,_lefty,_righty);
    }
    else if(L>_rightx || R<_leftx)return 0;
    long long mid=(L+R)/2;
    long long l=sumx(2*node,L,mid,_leftx,_rightx,_lefty,_righty);
    long long r=sumx(2*node+1,mid+1,R,_leftx,_rightx,_lefty,_righty);
    return gcd(l,r);
}
void updatey(long long nodex, long long Lx, long long Rx, long long nodey, long long Ly, long long Ry, long long row, long long col, long long val)
{
    if(Ly==Ry)
    {
        if(Lx==Rx)
        {
            tree[nodex][nodey]=val;
        }
        else
        {
            tree[nodex][nodey]=gcd(tree[2*nodex][nodey],tree[2*nodex+1][nodey]);
        }
    }
    else
    {
        long long mid=(Ly+Ry)/2;
        if(col>mid)updatey(nodex,Lx,Rx,2*nodey+1,mid+1,Ry,row,col,val);
        else updatey(nodex,Lx,Rx,2*nodey,Ly,mid,row,col,val);
        tree[nodex][nodey]=gcd(tree[nodex][2*nodey],tree[nodex][2*nodey+1]);
    }
}
void updatex(long long node, long long L, long long R, long long row, long long col, long long val)
{
    if(L!=R)
    {
        long long mid=(L+R)/2;
        if(row>mid)updatex(2*node+1,mid+1,R,row,col,val);
        else updatex(2*node,L,mid,row,col,val);
    }
    updatey(node,L,R,1,0,m-1,row,col,val);
}

long long calculate(int P, int Q, int U, int V)
{
    return sumx(1,0,n-1,P,U,Q,V);
}
void update(int P, int Q, long long K)
{
    updatex(1,0,n-1,P,Q,K);
}
/*
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>m;
    cout<<tree[1][1]<<endl;
    int q;
    cin>>q;
    for(int i=0; i<q; i++)
    {
        int type;
        cin>>type;
        if(type==1)
        {
            int r,c,val;
            cin>>r>>c>>val;
            updatex(1,0,n-1,r,c,val);
        }
        else
        {
            int gorelevox,gorelevoy,doludesnox,doludesnoy;
            cin>>gorelevox>>gorelevoy>>doludesnox>>doludesnoy;
            cout<<sumx(1,0,n-1,gorelevox,doludesnox,gorelevoy,doludesnoy)<<endl;
        }

    }
    return 0;
}

2 3
20 6 15
0 14 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 1628 KB Output is correct
3 Correct 1 ms 1628 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 1628 KB Output is correct
6 Correct 1 ms 1624 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 1628 KB Output is correct
10 Correct 1 ms 1628 KB Output is correct
11 Correct 1 ms 1580 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 482 ms 161048 KB Output is correct
5 Correct 357 ms 161304 KB Output is correct
6 Correct 423 ms 160124 KB Output is correct
7 Correct 429 ms 160144 KB Output is correct
8 Correct 394 ms 160084 KB Output is correct
9 Correct 449 ms 160080 KB Output is correct
10 Correct 404 ms 160084 KB Output is correct
11 Correct 1 ms 344 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 1628 KB Output is correct
3 Correct 1 ms 1628 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 1628 KB Output is correct
6 Correct 1 ms 1628 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 1624 KB Output is correct
10 Correct 2 ms 1624 KB Output is correct
11 Correct 1 ms 1628 KB Output is correct
12 Correct 657 ms 130492 KB Output is correct
13 Correct 818 ms 127072 KB Output is correct
14 Runtime error 115 ms 256000 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 1628 KB Output is correct
3 Correct 2 ms 1628 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 1628 KB Output is correct
6 Correct 1 ms 1628 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 1 ms 1580 KB Output is correct
10 Correct 1 ms 1628 KB Output is correct
11 Correct 1 ms 1628 KB Output is correct
12 Correct 473 ms 161012 KB Output is correct
13 Correct 355 ms 161300 KB Output is correct
14 Correct 421 ms 160080 KB Output is correct
15 Correct 433 ms 160084 KB Output is correct
16 Correct 378 ms 160104 KB Output is correct
17 Correct 409 ms 160152 KB Output is correct
18 Correct 393 ms 160080 KB Output is correct
19 Correct 656 ms 130384 KB Output is correct
20 Correct 794 ms 127060 KB Output is correct
21 Runtime error 117 ms 256000 KB Execution killed with signal 9
22 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 1628 KB Output is correct
3 Correct 1 ms 1628 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 1624 KB Output is correct
6 Correct 1 ms 1628 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 856 KB Output is correct
9 Correct 1 ms 1628 KB Output is correct
10 Correct 1 ms 1628 KB Output is correct
11 Correct 1 ms 1628 KB Output is correct
12 Correct 475 ms 160976 KB Output is correct
13 Correct 374 ms 161300 KB Output is correct
14 Correct 418 ms 160080 KB Output is correct
15 Correct 410 ms 160008 KB Output is correct
16 Correct 381 ms 160084 KB Output is correct
17 Correct 432 ms 160084 KB Output is correct
18 Correct 384 ms 160084 KB Output is correct
19 Correct 631 ms 130364 KB Output is correct
20 Correct 772 ms 126988 KB Output is correct
21 Runtime error 100 ms 256000 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -