oj.uz

Submission #1091127

# Submission time Handle Problem Language Result Execution time Memory
1091127 2024-09-19T22:07:03 Z AtinaR Game (IOI13_game) C++14
37 / 100
 790 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, vector<long long>(4*m));
}
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 1 ms 348 KB Output is correct
2 Correct 1 ms 1460 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 0 ms 604 KB Output is correct
9 Correct 1 ms 1624 KB Output is correct
10 Correct 1 ms 1628 KB Output is correct
11 Correct 1 ms 1628 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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 448 ms 132552 KB Output is correct
5 Correct 377 ms 133912 KB Output is correct
6 Correct 424 ms 131324 KB Output is correct
7 Correct 399 ms 131092 KB Output is correct
8 Correct 357 ms 131608 KB Output is correct
9 Correct 416 ms 131084 KB Output is correct
10 Correct 368 ms 130836 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 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 0 ms 604 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 650 ms 132212 KB Output is correct
13 Correct 789 ms 127988 KB Output is correct
14 Runtime error 118 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 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 0 ms 604 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 487 ms 129756 KB Output is correct
13 Correct 341 ms 133912 KB Output is correct
14 Correct 395 ms 131348 KB Output is correct
15 Correct 409 ms 131216 KB Output is correct
16 Correct 356 ms 131608 KB Output is correct
17 Correct 436 ms 131384 KB Output is correct
18 Correct 357 ms 130928 KB Output is correct
19 Correct 639 ms 133772 KB Output is correct
20 Correct 787 ms 130404 KB Output is correct
21 Runtime error 122 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 0 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 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 604 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 451 ms 129828 KB Output is correct
13 Correct 349 ms 133908 KB Output is correct
14 Correct 440 ms 131356 KB Output is correct
15 Correct 422 ms 131216 KB Output is correct
16 Correct 371 ms 131608 KB Output is correct
17 Correct 413 ms 131196 KB Output is correct
18 Correct 363 ms 130836 KB Output is correct
19 Correct 644 ms 133788 KB Output is correct
20 Correct 790 ms 130468 KB Output is correct
21 Runtime error 102 ms 256000 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -