답안 #640018

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
640018 2022-09-13T09:44:50 Z ggoh 말 (IOI15_horses) C++14
100 / 100
1294 ms 79496 KB
#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;
      |                      ~^~
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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