oj.uz

Submission #69061

# Submission time Handle Problem Language Result Execution time Memory
69061 2018-08-19T16:54:40 Z MKopchev Game (IOI13_game) C++14
63 / 100
 3756 ms 257024 KB 
#include<bits/stdc++.h>
#include "game.h"
using namespace std;
vector< vector<long long> > tree;
long long my_gcd(long long a,long long b)
{
    if(a==0||b==0)return a+b;
    long long r=a%b;
    while(r)
    {
        a=b;
        b=r;
        r=a%b;
    }
    return b;
}
int r,c;
void init(int R, int C)
{
    r=R;
    c=C;
    int u=1;
    while(u<R)u=u*2;
    u=u*2+5;

    int v=1;
    while(v<C)v=v*2;
    v=v*2+5;

    vector<long long> help={};
    for(int j=0;j<v;j++)help.push_back(0);
    for(int i=0;i<u;i++)
        {
        tree.push_back(help);
        }

}
void upd(int ind,int node,int l,int r,int pos,long long val,bool down)
{
    if(l==r)
    {
        assert(l==pos);
        if(down)tree[ind][node]=val;
        else tree[ind][node]=my_gcd(tree[ind*2][node],tree[ind*2+1][node]);
        //cout<<ind<<" "<<node<<" -> "<<val<<endl;
        return;
    }
    int av=(l+r)/2;
    if(pos<=av)upd(ind,node*2,l,av,pos,val,down);
    else upd(ind,node*2+1,av+1,r,pos,val,down);
    tree[ind][node]=my_gcd(tree[ind][node*2],tree[ind][node*2+1]);
}
void my_update(int node,int lx,int rx,int x,int y,long long val)
{
    if(lx==rx)
    {
        assert(lx==x);
        upd(node,1,0,c-1,y,val,1);
        return;
    }
    int av=(lx+rx)/2;
    if(x<=av)my_update(node*2,lx,av,x,y,val);
    else my_update(node*2+1,av+1,rx,x,y,val);
    upd(node,1,0,c-1,y,val,0);
}
void update(int P, int Q, long long K)
{
    my_update(1,0,r-1,P,Q,K);
}
long long que(int ind,int node,int l,int r,int lq,int rq)
{
    //cout<<ind<<" "<<node<<" "<<l<<" "<<r<<" "<<lq<<" "<<rq<<endl;
    if(l==lq&&r==rq)return tree[ind][node];
    int av=(l+r)/2;
    long long ans=0;
    if(lq<=av)ans=my_gcd(ans,que(ind,node*2,l,av,lq,min(av,rq)));
    if(av<rq)ans=my_gcd(ans,que(ind,node*2+1,av+1,r,max(av+1,lq),rq));
    return ans;
}
int lq_x,rq_x,lq_y,rq_y;
long long my_query(int node,int l,int r,int lq,int rq)
{
    //cout<<node<<" "<<l<<" "<<r<<" "<<lq<<" "<<rq<<endl;
    /*
    cout<<lx<<" "<<rx<<" "<<ly<<" "<<ry<<endl;
    cout<<"query: "<<lq_x<<" "<<rq_x<<" "<<lq_y<<" "<<rq_y<<endl;
    */
    if(l==lq&&r==rq)return que(node,1,0,c-1,lq_y,rq_y);
    int av=(l+r)/2;
    long long ans=0;
    if(lq<=av)ans=my_gcd(ans,my_query(node*2,l,av,lq,min(av,rq)));
    if(av<rq)ans=my_gcd(ans,my_query(node*2+1,av+1,r,max(av+1,lq),rq));
    return ans;
}
long long calculate(int P, int Q, int U, int V)
{
    lq_x=P;
    lq_y=Q;
    rq_x=U;
    rq_y=V;
    long long ans=my_query(1,0,r-1,lq_x,rq_x);
    /*
    for(int i=P;i<=U;i++)
        ans=my_gcd(ans,my_query(i,1,0,c-1,Q,V));
    */
    return ans;
}
/*
int main()
{

init(2,2);
update(0,0,30);
update(0,1,42);
update(1,0,70);
update(1,1,105);
for(int i1=0;i1<2;i1++)
    for(int j1=0;j1<2;j1++)
        for(int i2=i1;i2<2;i2++)
            for(int j2=j1;j2<2;j2++)
            {
            cout<<i1<<" "<<j1<<" "<<i2<<" "<<j2<<" -> "<<calculate(i1,j1,i2,j2)<<endl;
            }
}
*/

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1128 KB Output is correct
2 Correct 3 ms 1128 KB Output is correct
3 Correct 3 ms 1128 KB Output is correct
4 Correct 1292 ms 85072 KB Output is correct
5 Correct 1061 ms 89280 KB Output is correct
6 Correct 1146 ms 89280 KB Output is correct
7 Correct 1218 ms 89280 KB Output is correct
8 Correct 819 ms 89280 KB Output is correct
9 Correct 1103 ms 89280 KB Output is correct
10 Correct 866 ms 89280 KB Output is correct
11 Correct 3 ms 89280 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 89280 KB Output is correct
2 Correct 3 ms 89280 KB Output is correct
3 Correct 5 ms 89280 KB Output is correct
4 Correct 3 ms 89280 KB Output is correct
5 Correct 4 ms 89280 KB Output is correct
6 Correct 3 ms 89280 KB Output is correct
7 Correct 2 ms 89280 KB Output is correct
8 Correct 3 ms 89280 KB Output is correct
9 Correct 3 ms 89280 KB Output is correct
10 Correct 3 ms 89280 KB Output is correct
11 Correct 5 ms 89280 KB Output is correct
12 Correct 1705 ms 89280 KB Output is correct
13 Correct 2797 ms 89280 KB Output is correct
14 Correct 932 ms 155480 KB Output is correct
15 Correct 3668 ms 160212 KB Output is correct
16 Correct 407 ms 164364 KB Output is correct
17 Correct 2120 ms 169800 KB Output is correct
18 Correct 2604 ms 174816 KB Output is correct
19 Correct 2513 ms 180236 KB Output is correct
20 Correct 2472 ms 185156 KB Output is correct
21 Correct 3 ms 185156 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 185156 KB Output is correct
2 Correct 4 ms 185156 KB Output is correct
3 Correct 4 ms 185156 KB Output is correct
4 Correct 2 ms 185156 KB Output is correct
5 Correct 3 ms 185156 KB Output is correct
6 Correct 4 ms 185156 KB Output is correct
7 Correct 2 ms 185156 KB Output is correct
8 Correct 4 ms 185156 KB Output is correct
9 Correct 3 ms 185156 KB Output is correct
10 Correct 3 ms 185156 KB Output is correct
11 Correct 2 ms 185156 KB Output is correct
12 Correct 1197 ms 185156 KB Output is correct
13 Correct 933 ms 185156 KB Output is correct
14 Correct 981 ms 185156 KB Output is correct
15 Correct 1185 ms 185156 KB Output is correct
16 Correct 756 ms 185156 KB Output is correct
17 Correct 1027 ms 185156 KB Output is correct
18 Correct 876 ms 185156 KB Output is correct
19 Correct 1794 ms 185156 KB Output is correct
20 Correct 2900 ms 185156 KB Output is correct
21 Correct 1177 ms 197832 KB Output is correct
22 Correct 3438 ms 202504 KB Output is correct
23 Correct 374 ms 206624 KB Output is correct
24 Correct 2152 ms 211900 KB Output is correct
25 Correct 2470 ms 217260 KB Output is correct
26 Correct 2547 ms 222560 KB Output is correct
27 Correct 2554 ms 227400 KB Output is correct
28 Runtime error 3 ms 227400 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 227400 KB Output is correct
2 Correct 3 ms 227400 KB Output is correct
3 Correct 3 ms 227400 KB Output is correct
4 Correct 3 ms 227400 KB Output is correct
5 Correct 3 ms 227400 KB Output is correct
6 Correct 3 ms 227400 KB Output is correct
7 Correct 2 ms 227400 KB Output is correct
8 Correct 2 ms 227400 KB Output is correct
9 Correct 3 ms 227400 KB Output is correct
10 Correct 4 ms 227400 KB Output is correct
11 Correct 3 ms 227400 KB Output is correct
12 Correct 1311 ms 227400 KB Output is correct
13 Correct 942 ms 227400 KB Output is correct
14 Correct 1206 ms 227400 KB Output is correct
15 Correct 1098 ms 227400 KB Output is correct
16 Correct 854 ms 227400 KB Output is correct
17 Correct 993 ms 227400 KB Output is correct
18 Correct 848 ms 227400 KB Output is correct
19 Correct 1725 ms 227400 KB Output is correct
20 Correct 3279 ms 227400 KB Output is correct
21 Correct 1128 ms 239616 KB Output is correct
22 Correct 3756 ms 244292 KB Output is correct
23 Correct 412 ms 248440 KB Output is correct
24 Correct 2293 ms 253940 KB Output is correct
25 Runtime error 2593 ms 257024 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
26 Halted 0 ms 0 KB -