답안 #999647

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
999647	2024-06-16T01:57:54 Z	Alfraganus	말 (IOI15_horses)	C++17	17 / 100	1500 ms	20384 KB

horses

#include "horses.h"
#include <bits/stdc++.h>
using namespace std;

const long long mod = 1e9 + 7;
vector<long long> x, y;

struct SegTree {

	int size = 1;
	vector<long long> pr;

	void init(){
		while(size < (int)x.size())
			size <<= 1;
		pr.resize(size << 1, 1);
		build(0, 0, size);
	}

	void build(int ind, int lx, int rx){
		if(lx + 1 == rx){
			if(lx < x.size())
				pr[ind] = x[lx];
			return;
		}
		int mid = (lx + rx) >> 1;
		build((ind << 1) + 1, lx, mid);
		build((ind << 1) + 2, mid, rx);
		pr[ind] = (pr[(ind << 1) + 1] * pr[(ind << 1) + 2]) % mod;
	}

	long long get(int l, int r, int ind, int lx, int rx){
		if(l <= lx and rx <= r)
			return pr[ind];
		if(r <= lx or rx <= l)
			return 1ll;
		int mid = (lx + rx) >> 1;
		return (get(l, r, (ind << 1) + 1, lx, mid) * get(l, r, (ind << 1) + 2, mid, rx)) % mod;
	}

	long long get(int l, int r){
		long long ans = 1;
		for(int i = l; i < r; i ++)
			ans = (ans * x[i]) % mod;
		long long y = get(l, r, 0, 0, size);
		if(ans != y){
			while(1){

			}
		}
		return y;
	}
};

SegTree s;

int init(int n, int X[], int Y[]) {
	x.resize(n);
	y.resize(n);
	for(int i = 0; i < n; i ++)
		x[i] = X[i], y[i] = Y[i];
	s.init();
	long long y1 = 0, p = 1, ans = 1;
	for(int i = n - 1; i >= 0; i --){
		if(p > 1e9 or y1 * p > 1e9)
			return ans;
		if(y[i] > y1 * p){
			y1 = y[i];
			p = 1;
			ans = (y1 * s.get(0, i + 1)) % mod;
		}
		p = p * x[i];
	}
	return ans;
}

int updateX(int pos, int val) {
	x[pos] = val;
	long long ans = 1, p = 1;
	for(int i = 0; i < (int)x.size(); i ++)
		p = (p * x[i]) % mod, ans = (max(ans, p * y[i])) % mod;
	int res = ans;
	return res;
}

int updateY(int pos, int val) {
	y[pos] = val;
	long long ans = 1, p = 1;
	for(int i = 0; i < (int)y.size(); i ++)
		p = (p * x[i]) % mod, ans = (max(ans, p * y[i])) % mod;
	int res = ans;
	return res;
}

Compilation message

horses.cpp: In member function 'void SegTree::build(int, int, int)':
horses.cpp:22:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |    if(lx < x.size())
      |       ~~~^~~~~~~~~~
horses.cpp: In member function 'long long int SegTree::get(int, int)':
horses.cpp:45:13: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   45 |   long long y = get(l, r, 0, 0, size);
      |             ^
horses.cpp:6:22: note: shadowed declaration is here
    6 | vector<long long> x, y;
      |                      ^
horses.cpp: In function 'int init(int, int*, int*)':
horses.cpp:65:6: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
   65 |   if(p > 1e9 or y1 * p > 1e9)
      |      ^
horses.cpp:65:20: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
   65 |   if(p > 1e9 or y1 * p > 1e9)
      |                 ~~~^~~
horses.cpp:66:11: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   66 |    return ans;
      |           ^~~
horses.cpp:74:9: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   74 |  return ans;
      |         ^~~
horses.cpp: In function 'int updateX(int, int)':
horses.cpp:82:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   82 |  int res = ans;
      |            ^~~
horses.cpp: In function 'int updateY(int, int)':
horses.cpp:91:12: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   91 |  int res = ans;
      |            ^~~

Subtask #1
17.0 / 17.0

#	결과	메모리	Grader output
1	Correct	344 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct
5	Correct	348 KB	Output is correct
6	Correct	348 KB	Output is correct
7	Correct	348 KB	Output is correct
8	Correct	432 KB	Output is correct
9	Correct	348 KB	Output is correct
10	Correct	344 KB	Output is correct
11	Correct	348 KB	Output is correct
12	Correct	348 KB	Output is correct
13	Correct	348 KB	Output is correct
14	Correct	348 KB	Output is correct
15	Correct	348 KB	Output is correct
16	Correct	348 KB	Output is correct
17	Correct	348 KB	Output is correct
18	Correct	348 KB	Output is correct
19	Correct	348 KB	Output is correct
20	Correct	348 KB	Output is correct

Subtask #2
0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	436 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	344 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	436 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	1 ms	344 KB	Output is correct
20	Correct	0 ms	436 KB	Output is correct
21	Incorrect	0 ms	348 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Subtask #3
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1506 ms	20384 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	440 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	344 KB	Output is correct
17	Correct	0 ms	344 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Incorrect	0 ms	348 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Subtask #5
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	436 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	0 ms	344 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Incorrect	0 ms	348 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

답안 #999647

Compilation message

Subtask #1 17.0 / 17.0

Subtask #2 0 / 17.0

Subtask #3 0 / 20.0

Subtask #4 0 / 23.0

Subtask #5 0 / 23.0

Subtask #1
17.0 / 17.0

Subtask #2
0 / 17.0

Subtask #3
0 / 20.0

Subtask #4
0 / 23.0

Subtask #5
0 / 23.0