oj.uz

답안 #597254

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
597254 2022-07-15T19:54:30 Z Apiram 말 (IOI15_horses) C++14
100 / 100
 710 ms 57264 KB 
#include "horses.h"
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
struct dataa2{
	long long v = 0,index = 0;
	void add(long long val){
		v = val;
	}
};
struct dataa{
	long long v = 0;
	bool ok = 1;
	void add(long long val){
		v = val;
		//sum += val *(right - left + 1);
	}
};
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]);
	}
};
Segment_Tree st;
struct Segment_Tree2{
	vector<dataa2>tree;
	int N;
	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];
			tree[node].index = 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);
		N = n;
		build(0,0,n-1,arr,n);
	}
	dataa2 combine(dataa2 left,dataa2 right){
		dataa2 res = right;
		auto temp = st.query(0,0,N - 1,left.index + 1,right.index);
		bool ok = temp.ok;
		if (left.v > right.v && (ok && temp.v * right.v <= left.v)){
			res = left;
		}
		return res;
	}
	dataa2 query(long long node,long long left,long long right,long long qleft,long long qright){
		if (qright<left|| qleft > right)return {0,0};
		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_Tree2 st2;
int solve(){
	int N = (int)x.size();
	auto temp = st2.query(0,0,N - 1,0,N - 1);
	return (st.query(0,0,N - 1,0,temp.index).v * temp.v)%mod;
}
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);
	st2.init(N,y);
	return solve();
}

int updateX(int pos, int val) {	
	st.update(0,0,(int)x.size()-1,pos,pos,val);
	st2.update(0,0,(int)x.size() - 1,pos,pos,y[pos]);
	return solve();
}

int updateY(int pos, int val) {
	y[pos] = val;
	st2.update(0,0,(int)x.size() - 1,pos,pos,y[pos]);
	return solve();
}

Compilation message

horses.cpp: In member function 'dataa Segment_Tree::combine(dataa, dataa)':
horses.cpp:41:15: warning: conversion from 'long long int' to 'double' may change value [-Wconversion]
   41 |    if (left.v * right.v > 1e9)res.ok = false;
      |        ~~~~~~~^~~~~~~~~
horses.cpp: In member function 'void Segment_Tree2::init(long long int, std::vector<long long int>&)':
horses.cpp:89:7: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   89 |   N = n;
      |       ^
horses.cpp: In function 'int solve()':
horses.cpp:132:54: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
  132 |  return (st.query(0,0,N - 1,0,temp.index).v * temp.v)%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 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 300 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 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 296 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 296 KB Output is correct
20 Correct 1 ms 212 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 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 1 ms 304 KB Output is correct
8 Correct 0 ms 300 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 300 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 300 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 304 KB Output is correct
18 Correct 0 ms 224 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 296 KB Output is correct
23 Correct 2 ms 340 KB Output is correct
24 Correct 2 ms 340 KB Output is correct
25 Correct 2 ms 336 KB Output is correct
26 Correct 2 ms 316 KB Output is correct
27 Correct 2 ms 340 KB Output is correct
28 Correct 2 ms 312 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 2 ms 408 KB Output is correct
31 Correct 2 ms 340 KB Output is correct
32 Correct 2 ms 312 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 380 ms 44520 KB Output is correct
2 Correct 415 ms 57264 KB Output is correct
3 Correct 501 ms 48376 KB Output is correct
4 Correct 479 ms 52284 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 300 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 296 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 296 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 0 ms 296 KB Output is correct
21 Correct 1 ms 304 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 2 ms 340 KB Output is correct
24 Correct 2 ms 340 KB Output is correct
25 Correct 2 ms 340 KB Output is correct
26 Correct 2 ms 340 KB Output is correct
27 Correct 3 ms 312 KB Output is correct
28 Correct 2 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 2 ms 312 KB Output is correct
31 Correct 2 ms 340 KB Output is correct
32 Correct 2 ms 340 KB Output is correct
33 Correct 207 ms 47648 KB Output is correct
34 Correct 187 ms 47632 KB Output is correct
35 Correct 187 ms 54436 KB Output is correct
36 Correct 158 ms 54612 KB Output is correct
37 Correct 156 ms 45684 KB Output is correct
38 Correct 148 ms 46600 KB Output is correct
39 Correct 123 ms 45632 KB Output is correct
40 Correct 135 ms 49480 KB Output is correct
41 Correct 137 ms 45644 KB Output is correct
42 Correct 134 ms 45760 KB Output is correct
43 Correct 122 ms 49916 KB Output is correct
44 Correct 123 ms 49944 KB Output is correct

Subtask #5
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 300 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 300 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 296 KB Output is correct
15 Correct 1 ms 296 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 300 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 2 ms 312 KB Output is correct
24 Correct 2 ms 312 KB Output is correct
25 Correct 2 ms 316 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 2 ms 316 KB Output is correct
28 Correct 2 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 308 KB Output is correct
31 Correct 2 ms 340 KB Output is correct
32 Correct 2 ms 340 KB Output is correct
33 Correct 381 ms 48324 KB Output is correct
34 Correct 388 ms 57092 KB Output is correct
35 Correct 493 ms 48444 KB Output is correct
36 Correct 464 ms 52296 KB Output is correct
37 Correct 183 ms 47512 KB Output is correct
38 Correct 189 ms 47696 KB Output is correct
39 Correct 161 ms 54440 KB Output is correct
40 Correct 157 ms 54500 KB Output is correct
41 Correct 147 ms 45780 KB Output is correct
42 Correct 142 ms 46568 KB Output is correct
43 Correct 123 ms 45656 KB Output is correct
44 Correct 134 ms 49496 KB Output is correct
45 Correct 136 ms 45672 KB Output is correct
46 Correct 132 ms 45672 KB Output is correct
47 Correct 126 ms 50044 KB Output is correct
48 Correct 118 ms 49864 KB Output is correct
49 Correct 710 ms 49532 KB Output is correct
50 Correct 653 ms 49588 KB Output is correct
51 Correct 401 ms 56388 KB Output is correct
52 Correct 298 ms 55972 KB Output is correct
53 Correct 552 ms 47960 KB Output is correct
54 Correct 384 ms 48560 KB Output is correct
55 Correct 279 ms 46636 KB Output is correct
56 Correct 293 ms 51396 KB Output is correct
57 Correct 415 ms 47268 KB Output is correct
58 Correct 368 ms 47812 KB Output is correct
59 Correct 120 ms 49892 KB Output is correct