Submission #310523

#	Time	Username	Problem	Language	Result	Execution time	Memory
310523		mosiashvililuka	Horses (IOI15_horses)	C++14	100 / 100	521 ms	41464 KiB

horses

#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 (stderr)

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 / 17
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 23 / 23
• Subtask 5: 23 / 23