oj.uz

답안 #1086982

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1086982 2024-09-12T01:38:14 Z the_coding_pooh 말 (IOI15_horses) C++14
100 / 100
 432 ms 58452 KB 
#include "horses.h"
#include <bits/stdc++.h>
#define uwu return;

using namespace std;

const int SIZE = 5e5 + 5,  MOD = 1e9 + 7;

long long in_X[SIZE], in_Y[SIZE]; 

#define lc 2 * id
#define rc 2 * id + 1

struct ratio_query{
	long long rq_seg[4 * SIZE];
	
	void pull(int id){
		if(rq_seg[lc] == MOD || rq_seg[rc] == MOD) 
			rq_seg[id] = MOD;
		else{
			rq_seg[id] = rq_seg[lc] * rq_seg[rc];
			if(rq_seg[id] >= MOD) 
				rq_seg[id] = MOD;
		}
	}

	void build(int L, int R, int id){
		if(L == R){
			rq_seg[id] = in_X[L];
			return;
		}
		int M = (L + R) / 2;
		build(L, M, lc);
		build(M + 1, R, rc);
		pull(id);
		return;
	}

	void modify(int pos, int val, int L, int R, int id){
		if(L == R){
			in_X[pos] = val;
			rq_seg[id] = val;
			return;
		}

		int M = (L + R) / 2;
		if(pos <= M)
			modify(pos, val, L, M, lc);
		else
			modify(pos, val, M + 1, R, rc);
		pull(id);
		return;
	}

	long long query(int ql, int qr, int L, int R, int id){
		if(ql <= L && R <= qr){
			return rq_seg[id];
		}
		int M = (L + R) / 2;
		long long retl = 1, retr = 1;
		if(ql <= M) 
			retl = query(ql, min(M, qr), L, M, lc);
		if(qr > M)
			retr = query(max(ql, M + 1), qr, M + 1, R, rc);
		if(retl == MOD || retr == MOD) 
			return MOD;
		return (retl * retr >= MOD ? MOD : retl * retr);
	}
}rq;

struct node{
	long long pi_X, mx_tm, mx_pos;
}SEGTree[4 * SIZE];

#define nd SEGTree[id]
#define ln SEGTree[lc]
#define rn SEGTree[rc]

void pull(int id){
	long long tms = rq.query(ln.mx_pos + 1, rn.mx_pos, 0, SIZE - 1, 1);
	if(tms == MOD || tms * in_Y[rn.mx_pos] >= in_Y[ln.mx_pos]){
		nd.mx_tm = (ln.pi_X * rn.mx_tm) % MOD;
		nd.mx_pos = rn.mx_pos;
	}
	else{
		nd.mx_tm = ln.mx_tm;
		nd.mx_pos = ln.mx_pos;
	}
	nd.pi_X = (ln.pi_X * rn.pi_X) % MOD;
	return;
}


void build(int L, int R, int id){
	if(L == R){
		SEGTree[id].pi_X = in_X[L];
		SEGTree[id].mx_tm = (in_X[L] * in_Y[L]) % MOD; 
		SEGTree[id].mx_pos = L;
		return;
	}
	int M = (L + R) / 2;
	build(L, M, lc);
	build(M + 1, R, rc);
	pull(id);
	return;
}

void modify(int pos, int val, bool is_X, int L, int R, int id){
	if(L == R){
		if(is_X){
			in_X[pos] = val;
			SEGTree[id].pi_X = in_X[L];
			SEGTree[id].mx_tm = (in_X[L] * in_Y[L]) % MOD; 
			rq.modify(pos, val, 0, SIZE - 1, 1);
		}
		else{
			in_Y[pos] = val;
			SEGTree[id].mx_tm = (in_X[L] * in_Y[L]) % MOD; 
		}
		return;
	}
	int M = (L + R) / 2;
	if(pos <= M)
		modify(pos, val, is_X, L, M, lc);
	else
		modify(pos, val, is_X, M + 1, R, rc);
	pull(id);
	return;
}

int init(int N, int X[], int Y[]) {
	for(int i = 0; i < N; i++){
		in_X[i] = X[i];
		in_Y[i] = Y[i];
	}
	rq.build(0, SIZE - 1, 1);
	build(0, SIZE - 1, 1);
	return SEGTree[1].mx_tm;
}

int updateX(int pos, int val) {	
	modify(pos, val, 1, 0, SIZE - 1, 1);
	return SEGTree[1].mx_tm;
}

int updateY(int pos, int val) {
	modify(pos, val, 0, 0, SIZE - 1, 1);
	return SEGTree[1].mx_tm;
}

Compilation message

horses.cpp: In function 'void pull(int)':
horses.cpp:80:37: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   80 |  long long tms = rq.query(ln.mx_pos + 1, rn.mx_pos, 0, SIZE - 1, 1);
      |                                     ^
horses.cpp:80:45: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   80 |  long long tms = rq.query(ln.mx_pos + 1, rn.mx_pos, 0, SIZE - 1, 1);
      |                                             ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:138:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  138 |  return SEGTree[1].mx_tm;
      |         ~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:143:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  143 |  return SEGTree[1].mx_tm;
      |         ~~~~~~~~~~~^~~~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:148:20: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  148 |  return SEGTree[1].mx_tm;
      |         ~~~~~~~~~~~^~~~~

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 33084 KB Output is correct
2 Correct 54 ms 33108 KB Output is correct
3 Correct 54 ms 33108 KB Output is correct
4 Correct 54 ms 33104 KB Output is correct
5 Correct 53 ms 33108 KB Output is correct
6 Correct 53 ms 33108 KB Output is correct
7 Correct 57 ms 33108 KB Output is correct
8 Correct 53 ms 33204 KB Output is correct
9 Correct 54 ms 33104 KB Output is correct
10 Correct 53 ms 33104 KB Output is correct
11 Correct 53 ms 33252 KB Output is correct
12 Correct 54 ms 33104 KB Output is correct
13 Correct 55 ms 33104 KB Output is correct
14 Correct 53 ms 33104 KB Output is correct
15 Correct 52 ms 33108 KB Output is correct
16 Correct 56 ms 33104 KB Output is correct
17 Correct 58 ms 33104 KB Output is correct
18 Correct 53 ms 33296 KB Output is correct
19 Correct 54 ms 33104 KB Output is correct
20 Correct 53 ms 33228 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 33104 KB Output is correct
2 Correct 56 ms 33108 KB Output is correct
3 Correct 54 ms 33104 KB Output is correct
4 Correct 53 ms 33104 KB Output is correct
5 Correct 53 ms 33248 KB Output is correct
6 Correct 54 ms 33108 KB Output is correct
7 Correct 54 ms 33108 KB Output is correct
8 Correct 56 ms 33276 KB Output is correct
9 Correct 53 ms 33104 KB Output is correct
10 Correct 53 ms 33104 KB Output is correct
11 Correct 54 ms 33104 KB Output is correct
12 Correct 57 ms 33108 KB Output is correct
13 Correct 54 ms 33104 KB Output is correct
14 Correct 56 ms 33040 KB Output is correct
15 Correct 54 ms 33108 KB Output is correct
16 Correct 55 ms 33108 KB Output is correct
17 Correct 53 ms 33204 KB Output is correct
18 Correct 53 ms 33260 KB Output is correct
19 Correct 57 ms 33104 KB Output is correct
20 Correct 53 ms 33108 KB Output is correct
21 Correct 53 ms 33100 KB Output is correct
22 Correct 53 ms 33108 KB Output is correct
23 Correct 55 ms 33104 KB Output is correct
24 Correct 55 ms 33108 KB Output is correct
25 Correct 55 ms 33108 KB Output is correct
26 Correct 56 ms 33108 KB Output is correct
27 Correct 55 ms 33108 KB Output is correct
28 Correct 54 ms 33108 KB Output is correct
29 Correct 55 ms 33144 KB Output is correct
30 Correct 67 ms 33104 KB Output is correct
31 Correct 55 ms 33264 KB Output is correct
32 Correct 55 ms 33108 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 187 ms 45836 KB Output is correct
2 Correct 262 ms 58452 KB Output is correct
3 Correct 310 ms 49748 KB Output is correct
4 Correct 286 ms 53652 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 33108 KB Output is correct
2 Correct 56 ms 33252 KB Output is correct
3 Correct 52 ms 33056 KB Output is correct
4 Correct 53 ms 33108 KB Output is correct
5 Correct 52 ms 33052 KB Output is correct
6 Correct 55 ms 33108 KB Output is correct
7 Correct 59 ms 33108 KB Output is correct
8 Correct 53 ms 33104 KB Output is correct
9 Correct 52 ms 33108 KB Output is correct
10 Correct 53 ms 33116 KB Output is correct
11 Correct 53 ms 33276 KB Output is correct
12 Correct 59 ms 33156 KB Output is correct
13 Correct 53 ms 33120 KB Output is correct
14 Correct 53 ms 33104 KB Output is correct
15 Correct 55 ms 33104 KB Output is correct
16 Correct 58 ms 33112 KB Output is correct
17 Correct 56 ms 33108 KB Output is correct
18 Correct 56 ms 33108 KB Output is correct
19 Correct 53 ms 33268 KB Output is correct
20 Correct 53 ms 33208 KB Output is correct
21 Correct 53 ms 33076 KB Output is correct
22 Correct 56 ms 33108 KB Output is correct
23 Correct 55 ms 33104 KB Output is correct
24 Correct 55 ms 33104 KB Output is correct
25 Correct 57 ms 33108 KB Output is correct
26 Correct 62 ms 33248 KB Output is correct
27 Correct 55 ms 33104 KB Output is correct
28 Correct 62 ms 33108 KB Output is correct
29 Correct 58 ms 33228 KB Output is correct
30 Correct 56 ms 33104 KB Output is correct
31 Correct 57 ms 33104 KB Output is correct
32 Correct 54 ms 33112 KB Output is correct
33 Correct 122 ms 48968 KB Output is correct
34 Correct 124 ms 48976 KB Output is correct
35 Correct 106 ms 55888 KB Output is correct
36 Correct 102 ms 55820 KB Output is correct
37 Correct 92 ms 47188 KB Output is correct
38 Correct 83 ms 47952 KB Output is correct
39 Correct 73 ms 46928 KB Output is correct
40 Correct 84 ms 50868 KB Output is correct
41 Correct 85 ms 47032 KB Output is correct
42 Correct 77 ms 47188 KB Output is correct
43 Correct 76 ms 51160 KB Output is correct
44 Correct 75 ms 51284 KB Output is correct

Subtask #5
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 63 ms 33104 KB Output is correct
2 Correct 55 ms 33192 KB Output is correct
3 Correct 55 ms 33108 KB Output is correct
4 Correct 55 ms 33108 KB Output is correct
5 Correct 54 ms 33112 KB Output is correct
6 Correct 54 ms 33104 KB Output is correct
7 Correct 55 ms 33108 KB Output is correct
8 Correct 55 ms 33048 KB Output is correct
9 Correct 54 ms 33176 KB Output is correct
10 Correct 57 ms 33360 KB Output is correct
11 Correct 53 ms 33108 KB Output is correct
12 Correct 53 ms 33072 KB Output is correct
13 Correct 53 ms 33112 KB Output is correct
14 Correct 53 ms 33108 KB Output is correct
15 Correct 54 ms 33168 KB Output is correct
16 Correct 52 ms 33116 KB Output is correct
17 Correct 52 ms 33120 KB Output is correct
18 Correct 53 ms 33104 KB Output is correct
19 Correct 52 ms 33108 KB Output is correct
20 Correct 53 ms 33108 KB Output is correct
21 Correct 58 ms 33220 KB Output is correct
22 Correct 53 ms 33108 KB Output is correct
23 Correct 61 ms 33108 KB Output is correct
24 Correct 55 ms 33108 KB Output is correct
25 Correct 56 ms 33104 KB Output is correct
26 Correct 59 ms 33104 KB Output is correct
27 Correct 55 ms 33108 KB Output is correct
28 Correct 53 ms 33140 KB Output is correct
29 Correct 54 ms 33328 KB Output is correct
30 Correct 54 ms 33108 KB Output is correct
31 Correct 54 ms 33100 KB Output is correct
32 Correct 58 ms 33308 KB Output is correct
33 Correct 185 ms 49748 KB Output is correct
34 Correct 268 ms 58448 KB Output is correct
35 Correct 304 ms 49748 KB Output is correct
36 Correct 282 ms 53588 KB Output is correct
37 Correct 116 ms 48980 KB Output is correct
38 Correct 117 ms 48892 KB Output is correct
39 Correct 103 ms 55760 KB Output is correct
40 Correct 103 ms 55828 KB Output is correct
41 Correct 90 ms 47188 KB Output is correct
42 Correct 83 ms 47960 KB Output is correct
43 Correct 74 ms 46928 KB Output is correct
44 Correct 85 ms 50900 KB Output is correct
45 Correct 88 ms 47004 KB Output is correct
46 Correct 80 ms 47028 KB Output is correct
47 Correct 76 ms 51284 KB Output is correct
48 Correct 78 ms 51280 KB Output is correct
49 Correct 432 ms 50844 KB Output is correct
50 Correct 406 ms 50848 KB Output is correct
51 Correct 206 ms 57684 KB Output is correct
52 Correct 163 ms 57224 KB Output is correct
53 Correct 362 ms 49328 KB Output is correct
54 Correct 194 ms 49748 KB Output is correct
55 Correct 153 ms 48068 KB Output is correct
56 Correct 183 ms 52820 KB Output is correct
57 Correct 221 ms 48724 KB Output is correct
58 Correct 204 ms 49232 KB Output is correct
59 Correct 80 ms 51268 KB Output is correct