oj.uz

Submission #310523

# Submission time Handle Problem Language Result Execution time Memory
310523 2020-10-07T08:46:40 Z mosiashvililuka Horses (IOI15_horses) C++14
100 / 100
 521 ms 41464 KB 
#include "horses.h"
//
#include<bits/stdc++.h>
using namespace std;
const int N=1100009;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,tp,tes,t,X[1100009],Y[1100009],seg[N],seg2[N],seg3[N],za,mod=1000000007LL,x,y,xx,yy;
bool bo2[N],bo3[N];
void up(int q){
	if(q==0) return;
	x=X[seg[q*2]];y=Y[seg[q*2]];
	xx=X[seg[q*2+1]];yy=Y[seg[q*2+1]];
	if(bo3[q*2]==1||bo2[q*2+1]==1){
		seg[q]=seg[q*2+1];
	}else{
		bool bo=0;
		zx=seg3[q*2]*seg2[q*2+1];
		if(zx>mod) bo=1;
		zx%=mod;
		zx*=xx;
		if(zx>mod) bo=1;
		zx%=mod;
		zx*=yy;
		if(zx>mod) bo=1;
		zx%=mod;
		if(bo3[q*2]==1||bo2[q*2+1]==1) bo=1;
		if(bo==1||zx>y){
			seg[q]=seg[q*2+1];
		}else{
			seg[q]=seg[q*2];
		}
	}
	if(seg[q]==seg[q*2]){
		seg2[q]=seg2[q*2];
		bo2[q]=bo2[q*2];
		bool bo=0;
		zx=seg3[q*2]*seg2[q*2+1];
		if(zx>mod) bo=1;
		zx%=mod;
		zx*=xx;
		if(zx>mod) bo=1;
		zx%=mod;
		zx*=seg3[q*2+1];
		if(zx>mod) bo=1;
		zx%=mod;
		if(bo3[q*2]==1||bo2[q*2+1]==1||bo3[q*2+1]==1) bo=1;
		bo3[q]=bo;
		seg3[q]=zx;
	}else{
		seg3[q]=seg3[q*2+1];
		bo3[q]=bo3[q*2+1];
		bool bo=0;
		zx=seg2[q*2+1]*seg3[q*2];
		if(zx>mod) bo=1;
		zx%=mod;
		zx*=x;
		if(zx>mod) bo=1;
		zx%=mod;
		zx*=seg2[q*2];
		if(zx>mod) bo=1;
		zx%=mod;
		if(bo2[q*2+1]==1||bo3[q*2]==1||bo2[q*2]==1) bo=1;
		bo2[q]=bo;
		seg2[q]=zx;
	}
	up(q/2);
}
void upd(int q){
	seg[q+za-1]=q;
	seg2[q+za-1]=seg3[q+za-1]=1LL;
	bo2[q+za-1]=bo3[q+za-1]=0;
	up((q+za-1)/2);
}
//
int init(int N, int XX[], int YY[]) {
	a=N;
	for(i=1; i<=a; i++){
		X[i]=XX[i-1];Y[i]=YY[i-1];
	}
	za=1;
	while(za<a) za*=2;
	for(i=a+1; i<=za; i++){
		X[i]=1;Y[i]=1;
	}
	for(i=1; i<=za; i++){
		upd(i);
	}
	zx=seg2[1]*X[seg[1]];zx%=mod;
	zx*=Y[seg[1]];zx%=mod;
	return zx;
}

int updateX(int pos, int val) {	
	c=pos;d=val;
	c++;
	X[c]=d;
	upd(c);
	zx=seg2[1]*X[seg[1]];zx%=mod;
	zx*=Y[seg[1]];zx%=mod;
	return zx;
}

int updateY(int pos, int val) {
	c=pos;d=val;
	c++;
	Y[c]=d;
	upd(c);
	zx=seg2[1]*X[seg[1]];zx%=mod;
	zx*=Y[seg[1]];zx%=mod;
	return zx;
}

Compilation message

horses.cpp: In function 'void upd(int)':
horses.cpp:71:13: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   71 |  up((q+za-1)/2);
      |     ~~~~~~~~^~
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:74:35: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   74 | int init(int N, int XX[], int YY[]) {
      |                                   ^
horses.cpp:5:11: note: shadowed declaration is here
    5 | const int N=1100009;
      |           ^
horses.cpp:85:7: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   85 |   upd(i);
      |       ^
horses.cpp:89:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   89 |  return zx;
      |         ^~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:96:6: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   96 |  upd(c);
      |      ^
horses.cpp:99:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   99 |  return zx;
      |         ^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:106:6: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  106 |  upd(c);
      |      ^
horses.cpp:109:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  109 |  return zx;
      |         ^~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 0 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 0 ms 384 KB Output is correct
19 Correct 0 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 0 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 0 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Correct 1 ms 384 KB Output is correct
27 Correct 1 ms 384 KB Output is correct
28 Correct 1 ms 512 KB Output is correct
29 Correct 1 ms 384 KB Output is correct
30 Correct 1 ms 384 KB Output is correct
31 Correct 1 ms 384 KB Output is correct
32 Correct 1 ms 384 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 437 ms 40440 KB Output is correct
2 Correct 521 ms 40864 KB Output is correct
3 Correct 499 ms 41080 KB Output is correct
4 Correct 492 ms 41080 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 0 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 0 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 0 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 2 ms 512 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Correct 2 ms 384 KB Output is correct
27 Correct 1 ms 384 KB Output is correct
28 Correct 1 ms 512 KB Output is correct
29 Correct 1 ms 384 KB Output is correct
30 Correct 1 ms 384 KB Output is correct
31 Correct 2 ms 512 KB Output is correct
32 Correct 1 ms 384 KB Output is correct
33 Correct 395 ms 39332 KB Output is correct
34 Correct 390 ms 40184 KB Output is correct
35 Correct 386 ms 40312 KB Output is correct
36 Correct 389 ms 40296 KB Output is correct
37 Correct 375 ms 40316 KB Output is correct
38 Correct 364 ms 40312 KB Output is correct
39 Correct 374 ms 40056 KB Output is correct
40 Correct 370 ms 40184 KB Output is correct
41 Correct 368 ms 40184 KB Output is correct
42 Correct 362 ms 40184 KB Output is correct
43 Correct 366 ms 40184 KB Output is correct
44 Correct 367 ms 40184 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 0 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 0 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 0 ms 384 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 2 ms 384 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Correct 1 ms 384 KB Output is correct
27 Correct 1 ms 384 KB Output is correct
28 Correct 2 ms 384 KB Output is correct
29 Correct 1 ms 384 KB Output is correct
30 Correct 1 ms 384 KB Output is correct
31 Correct 1 ms 384 KB Output is correct
32 Correct 1 ms 512 KB Output is correct
33 Correct 429 ms 40312 KB Output is correct
34 Correct 510 ms 41464 KB Output is correct
35 Correct 491 ms 41080 KB Output is correct
36 Correct 493 ms 41080 KB Output is correct
37 Correct 394 ms 40184 KB Output is correct
38 Correct 388 ms 40184 KB Output is correct
39 Correct 386 ms 40312 KB Output is correct
40 Correct 388 ms 40184 KB Output is correct
41 Correct 371 ms 40184 KB Output is correct
42 Correct 358 ms 40184 KB Output is correct
43 Correct 364 ms 40104 KB Output is correct
44 Correct 370 ms 40184 KB Output is correct
45 Correct 364 ms 40184 KB Output is correct
46 Correct 368 ms 40352 KB Output is correct
47 Correct 369 ms 40068 KB Output is correct
48 Correct 366 ms 40184 KB Output is correct
49 Correct 510 ms 41088 KB Output is correct
50 Correct 511 ms 41080 KB Output is correct
51 Correct 455 ms 41380 KB Output is correct
52 Correct 444 ms 41244 KB Output is correct
53 Correct 502 ms 41080 KB Output is correct
54 Correct 428 ms 41224 KB Output is correct
55 Correct 441 ms 40312 KB Output is correct
56 Correct 438 ms 41208 KB Output is correct
57 Correct 447 ms 41080 KB Output is correct
58 Correct 443 ms 41148 KB Output is correct
59 Correct 363 ms 40244 KB Output is correct