oj.uz

답안 #597118

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
597118 2022-07-15T14:22:55 Z Apiram 말 (IOI15_horses) C++14
34 / 100
 1500 ms 27844 KB 
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
struct dataa{
	long long v = 0;
	bool ok = 1;
	void add(long long val){
		v = val;
		//sum += val *(right - left + 1);
	}
};
long long S,T;
struct Segment_Tree{
	vector<dataa>tree;
	void build(long long node,long long left,long long right,vector<long long>&arr,long long n){
		if (left == right){
			tree[node].v  = arr[left];
			return ;
		}
		long long mid = (left + right)>>1;
		long long z = node + ((mid - left + 1)<<1);
		build(node + 1,left,mid,arr,n);
		build(z,mid + 1,right,arr,n);
		tree[node] = combine(tree[node + 1],tree[z]);
	}
	void init(long long n,vector<long long>&arr){
		tree.resize(2*n - 1);
		build(0,0,n-1,arr,n);
	}
	dataa combine(dataa left,dataa right){
		dataa res;
		res.v = (left.v * right.v)%mod;
		res.ok = left.ok & right.ok;
		if (res.ok){
			if (left.v * right.v > 1e9)res.ok = false;
		}
		return res;
	}
	dataa query(long long node,long long left,long long right,long long qleft,long long qright){
		if (qright<left|| qleft > right)return {1,1};
		if (qleft<=left && qright>=right){
			return tree[node];
		}
		long long mid = (left + right)>>1;
		long long z = node + ((mid - left + 1)<<1);
		return combine(query(node + 1,left,mid,qleft,qright),query(z,mid + 1,right,qleft,qright));
	}
	void update(long long node,long long left,long long right,long long uleft,long long uright,long long v){
		if (left > uright || right < uleft) return;
		if (uleft <= left && right <=uright){
			tree[node].add(v);
			return;
		}
		long long mid = (left + right)>>1;
		long long z = node + ((mid - left + 1)<<1);
		if (uleft<=mid){
			update(node + 1,left,mid,uleft,uright,v);
		}
		if (uright > mid){
			update(z,mid + 1,right,uleft,uright,v);
		}
		tree[node] = combine(tree[node + 1],tree[z]);
	}
};
 
vector<long long>x,y;
Segment_Tree st;
int solve(){
	int N = (int)x.size();
	int ans = 0;
	long long maxxy = y[N - 1],index = N - 1;
	auto temp = st.query(0,0,N - 1,0,N - 1);
	ans = (temp.v * y[N - 1])%mod;
	for (int i = N - 2;i>=0;--i){
		temp = st.query(0,0,N - 1,i + 1,index);
		bool ok = temp.ok;
		//cout<<temp<<" "<<Y[i - 1] / Y[index]<<" "<<i<<" "<<maxxy<<" "<<index<<'\n';
		if (y[i] > maxxy && (ok && temp.v * y[index] <= y[i])){
			maxxy = y[i];
			index = i;
			temp = st.query(0,0,N - 1,0,i);
			ans = (temp.v * y[i])%mod;
		}
	}
	return ans;
}
int init(int N, int X[], int Y[]) {
	for (int i = 0;i<N;++i){
		x.push_back(X[i]);
		y.push_back(Y[i]);
	}
	st.init(N,x);
	return solve();
}
 
int updateX(int pos, int val) {	
	st.update(0,0,(int)x.size()-1,pos,pos,val);
	return solve();
}
 
int updateY(int pos, int val) {
	y[pos] = val;
	return solve();
}

Compilation message

horses.cpp: In member function 'dataa Segment_Tree::combine(dataa, dataa)':
horses.cpp:36:15: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
   36 |    if (left.v * right.v > 1e9)res.ok = false;
      |        ~~~~~~~^~~~~~~~~
horses.cpp: In function 'int solve()':
horses.cpp:74:27: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   74 |  ans = (temp.v * y[N - 1])%mod;
      |        ~~~~~~~~~~~~~~~~~~~^~~~
horses.cpp:83:25: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   83 |    ans = (temp.v * y[i])%mod;
      |          ~~~~~~~~~~~~~~~^~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 280 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 95 ms 340 KB Output is correct
24 Correct 93 ms 344 KB Output is correct
25 Correct 111 ms 348 KB Output is correct
26 Correct 56 ms 360 KB Output is correct
27 Correct 68 ms 356 KB Output is correct
28 Correct 118 ms 340 KB Output is correct
29 Correct 69 ms 340 KB Output is correct
30 Correct 63 ms 340 KB Output is correct
31 Correct 77 ms 352 KB Output is correct
32 Correct 97 ms 340 KB Output is correct

Subtask #3
0 / 20.0

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

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 86 ms 340 KB Output is correct
24 Correct 94 ms 340 KB Output is correct
25 Correct 94 ms 356 KB Output is correct
26 Correct 56 ms 340 KB Output is correct
27 Correct 71 ms 340 KB Output is correct
28 Correct 118 ms 464 KB Output is correct
29 Correct 68 ms 344 KB Output is correct
30 Correct 63 ms 340 KB Output is correct
31 Correct 71 ms 360 KB Output is correct
32 Correct 97 ms 348 KB Output is correct
33 Execution timed out 1573 ms 27844 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 86 ms 340 KB Output is correct
24 Correct 94 ms 360 KB Output is correct
25 Correct 101 ms 472 KB Output is correct
26 Correct 56 ms 340 KB Output is correct
27 Correct 73 ms 348 KB Output is correct
28 Correct 116 ms 340 KB Output is correct
29 Correct 68 ms 340 KB Output is correct
30 Correct 62 ms 360 KB Output is correct
31 Correct 74 ms 344 KB Output is correct
32 Correct 99 ms 340 KB Output is correct
33 Execution timed out 1594 ms 27824 KB Time limit exceeded
34 Halted 0 ms 0 KB -