답안 #160537

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
160537	2019-10-28T11:04:05 Z	FiloSanza	말 (IOI15_horses)	C++14	100 / 100	1251 ms	40524 KB

horses

#include "horses.h"
#include <bits/stdc++.h>

using namespace std;

constexpr int MOD = 1e9+7;

vector<pair<long long, bool>> segX;
vector<int> segY;
vector<int> Y;
int S;

inline int left(int i){return i*2+1;}
inline int right(int i){return (i+1)*2;}
inline int father(int i){return (i-1)/2;}

pair<long long, bool> mergeX(pair<long long, bool> a, pair<long long, bool> b){
	long long val = (a.first * b.first); 
	bool o = val >= MOD || a.second || b.second;
	return {val % MOD, o};
}

pair<long long, bool> queryX(int pos, int l, int h, int a, int b){
	if(h < a || l > b) return {1, false};
	if(l >= a && b >= h) return segX[pos];
	int mid = (l+h)/2;
	return mergeX(queryX(left(pos), l, mid, a, b), queryX(right(pos), mid+1, h, a, b));
}

int mergeY(int a, int b){
	auto query = queryX(0, 0, S/2, a+1, b);
	if(query.second) return b;
	return Y[a] < 1LL * query.first * Y[b] ? b : a;
}

int init(int N, int X[], int Y[]) {
	S = (1 << (int)ceil(log2(N) + 1)) - 1;
	segX.resize(S, {1, false});
	segY.resize(S, N);
	::Y.resize(N);
	for(int i=0; i<N; i++) ::Y[i] = Y[i];
	::Y.push_back(0);
	iota(segY.begin()+S/2, segY.begin()+S/2+N, 0);

	for(int i=0; i<N; i++) segX[i+S/2] = {X[i], false};

	for(int i=S/2-1; i>=0; i--){
		segX[i] = mergeX(segX[left(i)], segX[right(i)]);
		segY[i] = mergeY(segY[left(i)], segY[right(i)]);
	}

	return 1LL * queryX(0, 0, S/2, 0, segY[0]).first * Y[segY[0]] % MOD;
}

int updateX(int i, int val) {	
	i += S/2;
	segX[i].first = val;
	while(i != 0){
		i = father(i);
		segX[i] = mergeX(segX[left(i)], segX[right(i)]);
		segY[i] = mergeY(segY[left(i)], segY[right(i)]);
	}

	return 1LL * queryX(0, 0, S/2, 0, segY[0]).first * Y[segY[0]] % MOD;
}

int updateY(int i, int val) {
	Y[i] = val;
	i += S/2;
	while(i != 0){
		i = father(i);
		segX[i] = mergeX(segX[left(i)], segX[right(i)]);
		segY[i] = mergeY(segY[left(i)], segY[right(i)]);
	}

	return 1LL * queryX(0, 0, S/2, 0, segY[0]).first * Y[segY[0]] % MOD;
}

Compilation message

horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:36:33: warning: declaration of 'Y' shadows a global declaration [-Wshadow]
 int init(int N, int X[], int Y[]) {
                                 ^
horses.cpp:10:13: note: shadowed declaration is here
 vector<int> Y;
             ^
horses.cpp:52:64: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return 1LL * queryX(0, 0, S/2, 0, segY[0]).first * Y[segY[0]] % MOD;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:64:64: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return 1LL * queryX(0, 0, S/2, 0, segY[0]).first * Y[segY[0]] % MOD;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:76:64: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
  return 1LL * queryX(0, 0, S/2, 0, segY[0]).first * Y[segY[0]] % MOD;
         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

Subtask #1
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	256 KB	Output is correct
3	Correct	2 ms	256 KB	Output is correct
4	Correct	2 ms	256 KB	Output is correct
5	Correct	2 ms	380 KB	Output is correct
6	Correct	2 ms	256 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	2 ms	252 KB	Output is correct
11	Correct	2 ms	376 KB	Output is correct
12	Correct	2 ms	376 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	2 ms	252 KB	Output is correct
15	Correct	2 ms	376 KB	Output is correct
16	Correct	2 ms	376 KB	Output is correct
17	Correct	2 ms	256 KB	Output is correct
18	Correct	1 ms	128 KB	Output is correct
19	Correct	2 ms	376 KB	Output is correct
20	Correct	2 ms	256 KB	Output is correct

Subtask #2
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	256 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	256 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	2 ms	376 KB	Output is correct
12	Correct	6 ms	292 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	2 ms	376 KB	Output is correct
15	Correct	2 ms	256 KB	Output is correct
16	Correct	2 ms	376 KB	Output is correct
17	Correct	2 ms	376 KB	Output is correct
18	Correct	2 ms	256 KB	Output is correct
19	Correct	2 ms	376 KB	Output is correct
20	Correct	2 ms	376 KB	Output is correct
21	Correct	2 ms	376 KB	Output is correct
22	Correct	2 ms	256 KB	Output is correct
23	Correct	4 ms	504 KB	Output is correct
24	Correct	4 ms	504 KB	Output is correct
25	Correct	4 ms	504 KB	Output is correct
26	Correct	3 ms	380 KB	Output is correct
27	Correct	4 ms	376 KB	Output is correct
28	Correct	3 ms	376 KB	Output is correct
29	Correct	5 ms	376 KB	Output is correct
30	Correct	4 ms	504 KB	Output is correct
31	Correct	4 ms	376 KB	Output is correct
32	Correct	4 ms	376 KB	Output is correct

Subtask #3
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	719 ms	31604 KB	Output is correct
2	Correct	684 ms	40524 KB	Output is correct
3	Correct	813 ms	31700 KB	Output is correct
4	Correct	795 ms	35540 KB	Output is correct

Subtask #4
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	2 ms	256 KB	Output is correct
3	Correct	2 ms	256 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	256 KB	Output is correct
6	Correct	2 ms	256 KB	Output is correct
7	Correct	2 ms	252 KB	Output is correct
8	Correct	2 ms	256 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	2 ms	504 KB	Output is correct
12	Correct	2 ms	256 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	2 ms	376 KB	Output is correct
15	Correct	2 ms	380 KB	Output is correct
16	Correct	2 ms	376 KB	Output is correct
17	Correct	2 ms	376 KB	Output is correct
18	Correct	2 ms	376 KB	Output is correct
19	Correct	2 ms	376 KB	Output is correct
20	Correct	2 ms	376 KB	Output is correct
21	Correct	2 ms	376 KB	Output is correct
22	Correct	2 ms	256 KB	Output is correct
23	Correct	4 ms	504 KB	Output is correct
24	Correct	4 ms	404 KB	Output is correct
25	Correct	4 ms	504 KB	Output is correct
26	Correct	3 ms	504 KB	Output is correct
27	Correct	5 ms	376 KB	Output is correct
28	Correct	4 ms	380 KB	Output is correct
29	Correct	4 ms	376 KB	Output is correct
30	Correct	4 ms	504 KB	Output is correct
31	Correct	4 ms	376 KB	Output is correct
32	Correct	4 ms	376 KB	Output is correct
33	Correct	301 ms	32660 KB	Output is correct
34	Correct	295 ms	32632 KB	Output is correct
35	Correct	259 ms	39544 KB	Output is correct
36	Correct	238 ms	39544 KB	Output is correct
37	Correct	291 ms	30712 KB	Output is correct
38	Correct	216 ms	31736 KB	Output is correct
39	Correct	260 ms	30724 KB	Output is correct
40	Correct	232 ms	34552 KB	Output is correct
41	Correct	269 ms	30712 KB	Output is correct
42	Correct	266 ms	30712 KB	Output is correct
43	Correct	193 ms	35064 KB	Output is correct
44	Correct	189 ms	35024 KB	Output is correct

Subtask #5
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	256 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	256 KB	Output is correct
7	Correct	2 ms	256 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	2 ms	380 KB	Output is correct
11	Correct	2 ms	376 KB	Output is correct
12	Correct	2 ms	376 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	2 ms	380 KB	Output is correct
15	Correct	2 ms	256 KB	Output is correct
16	Correct	2 ms	376 KB	Output is correct
17	Correct	2 ms	256 KB	Output is correct
18	Correct	8 ms	376 KB	Output is correct
19	Correct	2 ms	376 KB	Output is correct
20	Correct	2 ms	376 KB	Output is correct
21	Correct	2 ms	376 KB	Output is correct
22	Correct	2 ms	376 KB	Output is correct
23	Correct	4 ms	376 KB	Output is correct
24	Correct	6 ms	504 KB	Output is correct
25	Correct	4 ms	504 KB	Output is correct
26	Correct	3 ms	504 KB	Output is correct
27	Correct	4 ms	376 KB	Output is correct
28	Correct	3 ms	376 KB	Output is correct
29	Correct	4 ms	376 KB	Output is correct
30	Correct	4 ms	504 KB	Output is correct
31	Correct	4 ms	380 KB	Output is correct
32	Correct	4 ms	376 KB	Output is correct
33	Correct	708 ms	31544 KB	Output is correct
34	Correct	634 ms	40396 KB	Output is correct
35	Correct	809 ms	31720 KB	Output is correct
36	Correct	789 ms	35504 KB	Output is correct
37	Correct	298 ms	32632 KB	Output is correct
38	Correct	295 ms	32636 KB	Output is correct
39	Correct	447 ms	39544 KB	Output is correct
40	Correct	231 ms	39416 KB	Output is correct
41	Correct	291 ms	30840 KB	Output is correct
42	Correct	215 ms	31736 KB	Output is correct
43	Correct	266 ms	30760 KB	Output is correct
44	Correct	233 ms	34680 KB	Output is correct
45	Correct	256 ms	30712 KB	Output is correct
46	Correct	261 ms	30840 KB	Output is correct
47	Correct	196 ms	35064 KB	Output is correct
48	Correct	189 ms	35064 KB	Output is correct
49	Correct	1199 ms	32940 KB	Output is correct
50	Correct	1233 ms	32828 KB	Output is correct
51	Correct	786 ms	39912 KB	Output is correct
52	Correct	500 ms	39672 KB	Output is correct
53	Correct	1251 ms	31480 KB	Output is correct
54	Correct	577 ms	31736 KB	Output is correct
55	Correct	932 ms	30816 KB	Output is correct
56	Correct	710 ms	34680 KB	Output is correct
57	Correct	877 ms	30812 KB	Output is correct
58	Correct	916 ms	31316 KB	Output is correct
59	Correct	189 ms	35064 KB	Output is correct

답안 #160537

Compilation message

Subtask #1 17.0 / 17.0

Subtask #2 17.0 / 17.0

Subtask #3 20.0 / 20.0

Subtask #4 23.0 / 23.0

Subtask #5 23.0 / 23.0

Subtask #1
17.0 / 17.0

Subtask #2
17.0 / 17.0

Subtask #3
20.0 / 20.0

Subtask #4
23.0 / 23.0

Subtask #5
23.0 / 23.0