Submission #640018

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
640018	2022-09-13T09:44:50 Z	ggoh	Horses (IOI15_horses)	C++14	100 / 100	1294 ms	79496 KB

horses

#include "horses.h"
#include<bits/stdc++.h>
using namespace std;
#define sz(v) ((int)(v).size())
typedef long long lint;
typedef pair<int,int> pii;

lint Z=1e9+7;
int n;
lint po(lint p,int q)
{
	if(q==0)return 1;
	if(q==1)return p;
	lint o=po(p,q/2);
	o=o*o%Z;
	if(q%2)o=o*p%Z;
	return o;
}
struct Tree{
	long double l;
	lint v;
}seg[1<<20];
long double lazyL[1<<20];
lint lazyV[1<<20];
vector<int>XX,YY;

void push(int num,int s,int e)
{
	seg[num].l+=lazyL[num];
	if(s!=e)
	{
		lazyL[2*num]+=lazyL[num];
		lazyL[2*num+1]+=lazyL[num];
	}
	lazyL[num]=0;
	seg[num].v=seg[num].v*lazyV[num]%Z;
	if(s!=e)
	{
		lazyV[2*num]=lazyV[2*num]*lazyV[num]%Z;
		lazyV[2*num+1]=lazyV[2*num+1]*lazyV[num]%Z;
	}
	lazyV[num]=1;
}
void update(int num,int s,int e,int l,int r,long double x,lint z)
{
	push(num,s,e);
	if(s>r||l>e)return ;
	if(l<=s&&e<=r)
	{
		seg[num].l+=x;
		seg[num].v=seg[num].v*z%Z;
		if(s!=e)
		{
			lazyL[num*2]+=x;
			lazyL[num*2+1]+=x;
			lazyV[num*2]=lazyV[num*2]*z%Z;
			lazyV[num*2+1]=lazyV[num*2+1]*z%Z;
		}
		return ;
	}
	update(num*2,s,(s+e)/2,l,r,x,z);
	update(num*2+1,(s+e)/2+1,e,l,r,x,z);
	if(seg[num*2].l>seg[num*2+1].l)
	{
		seg[num].l=seg[num*2].l;
		seg[num].v=seg[num*2].v;
	}
	else
	{
		seg[num].l=seg[num*2+1].l;
		seg[num].v=seg[num*2+1].v;
	}
}

int init(int N, int X[], int Y[]) {
	n=N;
	for(int i=1;i<(1<<20);i++)lazyV[i]=seg[i].v=1;
	for(int i=0;i<n;i++)
	{
		long double x=log(X[i]);
		long double y=log(Y[i]);
		XX.push_back(X[i]);
		YY.push_back(Y[i]);
		update(1,0,n-1,i,n-1,x,X[i]);
		update(1,0,n-1,i,i,y,Y[i]);
	}
	return (int)seg[1].v;
}

int updateX(int pos, int val) {
	long double x0=log(XX[pos]);
	long double x1=log(val);
	lint mul=po(XX[pos],Z-2)*val%Z;
	XX[pos]=val;
	update(1,0,n-1,pos,n-1,x1-x0,mul);
	return (int)seg[1].v;
}

int updateY(int pos, int val) {
	long double y0=log(YY[pos]);
	long double y1=log(val);
	lint mul=po(YY[pos],Z-2)*val%Z;
	YY[pos]=val;
	update(1,0,n-1,pos,pos,y1-y0,mul);
	return (int)seg[1].v;
}

Compilation message

horses.cpp: In function 'int updateX(int, int)':
horses.cpp:93:23: warning: conversion from 'lint' {aka 'long long int'} to 'int' may change value [-Wconversion]
   93 |  lint mul=po(XX[pos],Z-2)*val%Z;
      |                      ~^~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:102:23: warning: conversion from 'lint' {aka 'long long int'} to 'int' may change value [-Wconversion]
  102 |  lint mul=po(YY[pos],Z-2)*val%Z;
      |                      ~^~

Subtask #1

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	41300 KB	Output is correct
2	Correct	16 ms	41288 KB	Output is correct
3	Correct	16 ms	41320 KB	Output is correct
4	Correct	16 ms	41424 KB	Output is correct
5	Correct	19 ms	41300 KB	Output is correct
6	Correct	18 ms	41300 KB	Output is correct
7	Correct	16 ms	41268 KB	Output is correct
8	Correct	16 ms	41300 KB	Output is correct
9	Correct	20 ms	41300 KB	Output is correct
10	Correct	18 ms	41300 KB	Output is correct
11	Correct	16 ms	41264 KB	Output is correct
12	Correct	17 ms	41300 KB	Output is correct
13	Correct	16 ms	41300 KB	Output is correct
14	Correct	19 ms	41324 KB	Output is correct
15	Correct	16 ms	41240 KB	Output is correct
16	Correct	16 ms	41300 KB	Output is correct
17	Correct	16 ms	41300 KB	Output is correct
18	Correct	17 ms	41268 KB	Output is correct
19	Correct	17 ms	41240 KB	Output is correct
20	Correct	17 ms	41260 KB	Output is correct

Subtask #2

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	41216 KB	Output is correct
2	Correct	16 ms	41332 KB	Output is correct
3	Correct	17 ms	41324 KB	Output is correct
4	Correct	17 ms	41236 KB	Output is correct
5	Correct	17 ms	41288 KB	Output is correct
6	Correct	17 ms	41292 KB	Output is correct
7	Correct	17 ms	41268 KB	Output is correct
8	Correct	17 ms	41300 KB	Output is correct
9	Correct	16 ms	41232 KB	Output is correct
10	Correct	17 ms	41300 KB	Output is correct
11	Correct	16 ms	41300 KB	Output is correct
12	Correct	18 ms	41244 KB	Output is correct
13	Correct	20 ms	41312 KB	Output is correct
14	Correct	17 ms	41316 KB	Output is correct
15	Correct	17 ms	41256 KB	Output is correct
16	Correct	17 ms	41340 KB	Output is correct
17	Correct	17 ms	41300 KB	Output is correct
18	Correct	16 ms	41300 KB	Output is correct
19	Correct	15 ms	41300 KB	Output is correct
20	Correct	17 ms	41324 KB	Output is correct
21	Correct	17 ms	41300 KB	Output is correct
22	Correct	16 ms	41288 KB	Output is correct
23	Correct	19 ms	41304 KB	Output is correct
24	Correct	18 ms	41428 KB	Output is correct
25	Correct	19 ms	41404 KB	Output is correct
26	Correct	18 ms	41428 KB	Output is correct
27	Correct	17 ms	41332 KB	Output is correct
28	Correct	19 ms	41324 KB	Output is correct
29	Correct	19 ms	41300 KB	Output is correct
30	Correct	19 ms	41428 KB	Output is correct
31	Correct	19 ms	41428 KB	Output is correct
32	Correct	19 ms	41292 KB	Output is correct

Subtask #3

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1080 ms	70648 KB	Output is correct
2	Correct	1290 ms	79496 KB	Output is correct
3	Correct	1164 ms	70588 KB	Output is correct
4	Correct	1203 ms	74408 KB	Output is correct

Subtask #4

23.0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	41252 KB	Output is correct
2	Correct	18 ms	41264 KB	Output is correct
3	Correct	17 ms	41300 KB	Output is correct
4	Correct	16 ms	41256 KB	Output is correct
5	Correct	18 ms	41272 KB	Output is correct
6	Correct	16 ms	41232 KB	Output is correct
7	Correct	16 ms	41324 KB	Output is correct
8	Correct	17 ms	41300 KB	Output is correct
9	Correct	17 ms	41300 KB	Output is correct
10	Correct	17 ms	41428 KB	Output is correct
11	Correct	15 ms	41272 KB	Output is correct
12	Correct	16 ms	41248 KB	Output is correct
13	Correct	17 ms	41264 KB	Output is correct
14	Correct	17 ms	41304 KB	Output is correct
15	Correct	17 ms	41300 KB	Output is correct
16	Correct	17 ms	41272 KB	Output is correct
17	Correct	17 ms	41284 KB	Output is correct
18	Correct	17 ms	41300 KB	Output is correct
19	Correct	16 ms	41328 KB	Output is correct
20	Correct	17 ms	41304 KB	Output is correct
21	Correct	17 ms	41260 KB	Output is correct
22	Correct	17 ms	41252 KB	Output is correct
23	Correct	20 ms	41344 KB	Output is correct
24	Correct	18 ms	41412 KB	Output is correct
25	Correct	18 ms	41384 KB	Output is correct
26	Correct	18 ms	41428 KB	Output is correct
27	Correct	22 ms	41428 KB	Output is correct
28	Correct	19 ms	41412 KB	Output is correct
29	Correct	18 ms	41300 KB	Output is correct
30	Correct	18 ms	41428 KB	Output is correct
31	Correct	20 ms	41344 KB	Output is correct
32	Correct	23 ms	41404 KB	Output is correct
33	Correct	993 ms	69820 KB	Output is correct
34	Correct	998 ms	69768 KB	Output is correct
35	Correct	1063 ms	76808 KB	Output is correct
36	Correct	1035 ms	76668 KB	Output is correct
37	Correct	958 ms	68016 KB	Output is correct
38	Correct	972 ms	68892 KB	Output is correct
39	Correct	943 ms	67828 KB	Output is correct
40	Correct	1037 ms	71904 KB	Output is correct
41	Correct	1010 ms	68060 KB	Output is correct
42	Correct	977 ms	67996 KB	Output is correct
43	Correct	1056 ms	72300 KB	Output is correct
44	Correct	1002 ms	72248 KB	Output is correct

Subtask #5

23.0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	41268 KB	Output is correct
2	Correct	15 ms	41264 KB	Output is correct
3	Correct	15 ms	41300 KB	Output is correct
4	Correct	16 ms	41260 KB	Output is correct
5	Correct	16 ms	41260 KB	Output is correct
6	Correct	16 ms	41264 KB	Output is correct
7	Correct	18 ms	41300 KB	Output is correct
8	Correct	16 ms	41300 KB	Output is correct
9	Correct	16 ms	41300 KB	Output is correct
10	Correct	16 ms	41300 KB	Output is correct
11	Correct	17 ms	41316 KB	Output is correct
12	Correct	16 ms	41300 KB	Output is correct
13	Correct	18 ms	41320 KB	Output is correct
14	Correct	17 ms	41332 KB	Output is correct
15	Correct	16 ms	41300 KB	Output is correct
16	Correct	16 ms	41300 KB	Output is correct
17	Correct	17 ms	41268 KB	Output is correct
18	Correct	16 ms	41256 KB	Output is correct
19	Correct	18 ms	41308 KB	Output is correct
20	Correct	19 ms	41400 KB	Output is correct
21	Correct	16 ms	41280 KB	Output is correct
22	Correct	16 ms	41252 KB	Output is correct
23	Correct	20 ms	41424 KB	Output is correct
24	Correct	19 ms	41428 KB	Output is correct
25	Correct	22 ms	41360 KB	Output is correct
26	Correct	17 ms	41364 KB	Output is correct
27	Correct	18 ms	41404 KB	Output is correct
28	Correct	18 ms	41376 KB	Output is correct
29	Correct	18 ms	41300 KB	Output is correct
30	Correct	18 ms	41428 KB	Output is correct
31	Correct	19 ms	41372 KB	Output is correct
32	Correct	19 ms	41420 KB	Output is correct
33	Correct	1077 ms	70612 KB	Output is correct
34	Correct	1294 ms	79424 KB	Output is correct
35	Correct	1193 ms	70688 KB	Output is correct
36	Correct	1285 ms	74392 KB	Output is correct
37	Correct	991 ms	69788 KB	Output is correct
38	Correct	1012 ms	69792 KB	Output is correct
39	Correct	1058 ms	76648 KB	Output is correct
40	Correct	1049 ms	76788 KB	Output is correct
41	Correct	967 ms	67984 KB	Output is correct
42	Correct	985 ms	68852 KB	Output is correct
43	Correct	968 ms	67888 KB	Output is correct
44	Correct	1026 ms	71744 KB	Output is correct
45	Correct	946 ms	67960 KB	Output is correct
46	Correct	960 ms	68020 KB	Output is correct
47	Correct	1020 ms	72300 KB	Output is correct
48	Correct	1020 ms	72136 KB	Output is correct
49	Correct	1200 ms	71832 KB	Output is correct
50	Correct	1195 ms	72120 KB	Output is correct
51	Correct	1156 ms	78568 KB	Output is correct
52	Correct	1176 ms	78112 KB	Output is correct
53	Correct	1148 ms	70276 KB	Output is correct
54	Correct	1104 ms	70612 KB	Output is correct
55	Correct	1102 ms	68912 KB	Output is correct
56	Correct	1186 ms	73636 KB	Output is correct
57	Correct	1080 ms	69568 KB	Output is correct
58	Correct	1063 ms	70128 KB	Output is correct
59	Correct	1002 ms	72232 KB	Output is correct