oj.uz

Submission #235367

# Submission time Handle Problem Language Result Execution time Memory
235367 2020-05-28T07:13:24 Z crossing0ver Game (IOI13_game) C++17
37 / 100
 1095 ms 23632 KB 
#include<bits/stdc++.h>
#define ll long long
#include "game.h"
using namespace std;

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 t[100][4*100001] , R, C;
ll t1[2000][4*2001];
void upd (int s,int v,int tl,int tr,int pos,ll val) {
	if (tl == tr) {
		t[s][v] = val;
		return;
	}
	int tm = (tl + tr)/2;
	if (pos <= tm) upd(s,v*2,tl,tm,pos,val);
	else upd(s,v*2|1,tm+1,tr,pos,val);
	t[s][v] = gcd2(t[s][v*2],t[s][v*2|1]);
}
void upd1 (int s,int v,int tl,int tr,int pos,ll val) {
	if (tl == tr) {
		t1[s][v] = val;
		return;
	}
	int tm = (tl + tr)/2;
	if (pos <= tm) upd(s,v*2,tl,tm,pos,val);
	else upd(s,v*2|1,tm+1,tr,pos,val);
	t1[s][v] = gcd2(t1[s][v*2],t1[s][v*2|1]);
}
ll get (int s,int v,int tl,int tr,int l,int r) {
	if (l > tr || r < tl) return 0;
	if (l <= tl && r >= tr) {
		return t[s][v];
	}
	int tm = (tl + tr)/2;
	return gcd2 ( get (s,v*2,tl,tm,l,r), get (s,v*2|1,tm+1,tr,l,r));
}
ll get1 (int s,int v,int tl,int tr,int l,int r) {
	if (l > tr || r < tl) return 0;
	if (l <= tl && r >= tr) {
		return t1[s][v];
	}
	int tm = (tl + tr)/2;
	return gcd2 ( get (s,v*2,tl,tm,l,r), get (s,v*2|1,tm+1,tr,l,r));
}
void update(int P, int Q, long long K) {
	if (C > 2000 || R > 2000)
	upd (P,1,0,100000,Q,K);
	else  upd1 (P,1,0,2000,Q,K);
}

long long calculate(int P, int Q, int U, int V) {
    /* ... */
    ll s = 0;
    for (int i = P; i <= U; i++) {
    	if (C > 2000 || R > 2000)
    	s = gcd2(s,get (i,1,0,100000,Q,V));
		else s = s = gcd2(s,get (i,1,0,2000,Q,V));	
	}
	return s;
}

void init(int R1, int C1) {R = R1; C = C1;}

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;
      ^~~
game.cpp: In function 'long long int calculate(int, int, int, int)':
game.cpp:65:10: warning: operation on 's' may be undefined [-Wsequence-point]
   else s = s = gcd2(s,get (i,1,0,2000,Q,V)); 
        ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 7 ms 2048 KB Output is correct
3 Correct 6 ms 2048 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 768 KB Output is correct
6 Correct 6 ms 1920 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 768 KB Output is correct
9 Correct 6 ms 1920 KB Output is correct
10 Correct 6 ms 1280 KB Output is correct
11 Correct 5 ms 768 KB Output is correct
12 Correct 5 ms 384 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 276 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 1070 ms 22872 KB Output is correct
5 Correct 679 ms 23160 KB Output is correct
6 Correct 844 ms 23628 KB Output is correct
7 Correct 890 ms 23264 KB Output is correct
8 Correct 696 ms 22000 KB Output is correct
9 Correct 877 ms 23416 KB Output is correct
10 Correct 778 ms 23072 KB Output is correct
11 Correct 5 ms 384 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 2048 KB Output is correct
3 Correct 6 ms 2048 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 5 ms 768 KB Output is correct
6 Correct 6 ms 1920 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 768 KB Output is correct
9 Correct 6 ms 1920 KB Output is correct
10 Correct 5 ms 1280 KB Output is correct
11 Correct 5 ms 768 KB Output is correct
12 Runtime error 23 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 6 ms 2048 KB Output is correct
3 Correct 6 ms 1972 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 6 ms 768 KB Output is correct
6 Correct 7 ms 1920 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 768 KB Output is correct
9 Correct 6 ms 1920 KB Output is correct
10 Correct 5 ms 1280 KB Output is correct
11 Correct 5 ms 768 KB Output is correct
12 Correct 1065 ms 22864 KB Output is correct
13 Correct 656 ms 23416 KB Output is correct
14 Correct 861 ms 23632 KB Output is correct
15 Correct 885 ms 23264 KB Output is correct
16 Correct 703 ms 21880 KB Output is correct
17 Correct 868 ms 23340 KB Output is correct
18 Correct 783 ms 22904 KB Output is correct
19 Runtime error 22 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 8 ms 2048 KB Output is correct
3 Correct 6 ms 2048 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 768 KB Output is correct
6 Correct 5 ms 1920 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 768 KB Output is correct
9 Correct 6 ms 1920 KB Output is correct
10 Correct 6 ms 1280 KB Output is correct
11 Correct 5 ms 768 KB Output is correct
12 Correct 1036 ms 22776 KB Output is correct
13 Correct 654 ms 23136 KB Output is correct
14 Correct 839 ms 23520 KB Output is correct
15 Correct 1095 ms 23288 KB Output is correct
16 Correct 716 ms 21944 KB Output is correct
17 Correct 823 ms 23320 KB Output is correct
18 Correct 745 ms 23096 KB Output is correct
19 Runtime error 25 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -