oj.uz

Submission #922380

# Submission time Handle Problem Language Result Execution time Memory
922380 2024-02-05T12:58:05 Z pcc RMQ (NOI17_rmq) C++14
30 / 100
 77 ms 13584 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>


const int mxn = 1e5+10;
vector<int> op[mxn];
int N,Q;
tuple<int,int,int> req[mxn];
int arr[mxn];
int segtree[mxn*4];

void build(int now,int l,int r){
	if(l == r){
		segtree[now] = arr[l];
		return;
	}
	int mid = (l+r)>>1;
	build(now*2+1,l,mid);
	build(now*2+2,mid+1,r);
	segtree[now] = min(segtree[now*2+1],segtree[now*2+2]);
}
int getval(int now,int l,int r,int s,int e){
	if(l >=s&&e>=r)return segtree[now];
	int mid = (l+r)>>1;
	if(mid>=e)return getval(now*2+1,l,mid,s,e);
	else if(mid<s)return getval(now*2+2,mid+1,r,s,e);
	else return min(getval(now*2+1,l,mid,s,e),getval(now*2+2,mid+1,r,s,e));
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>Q;
	for(int i = 0;i<Q;i++){
		int s,e,v;
		cin>>s>>e>>v;
		req[i] = make_tuple(s,e,v);
		v++;
		op[s].push_back(v);
		op[e+1].push_back(-v);
	}
	multiset<int> st;
	st.insert(0);
	for(int i = 0;i<N;i++){
		for(auto &j:op[i]){
			if(j>0)st.insert(j-1);
			else st.erase(st.find(-j-1));
		}
		arr[i] = *st.rbegin();
	}
	build(0,0,N-1);
	bool flag = true;
	for(int i = 0;i<Q;i++){
		int s = get<0>(req[i]),e = get<1>(req[i]),v = get<2>(req[i]);
		if(getval(0,0,N-1,s,e) != v){
			flag = false;
		}
	}
	if(flag)for(int i = 0;i<N;i++)cout<<arr[i]<<' ';
	else for(int i = 0;i<N;i++)cout<<-1<<' ';
	return 0;
}

Subtask #1
6.9 / 23.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 5724 KB Output is partially correct
2 Partially correct 2 ms 5724 KB Output is partially correct
3 Partially correct 1 ms 5724 KB Output is partially correct
4 Partially correct 1 ms 5552 KB Output is partially correct
5 Partially correct 1 ms 5724 KB Output is partially correct
6 Correct 1 ms 5724 KB Output is correct
7 Correct 2 ms 5724 KB Output is correct
8 Correct 1 ms 5724 KB Output is correct
9 Correct 2 ms 5724 KB Output is correct
10 Correct 2 ms 5768 KB Output is correct
11 Partially correct 2 ms 5724 KB Output is partially correct

Subtask #2
13.2 / 44.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 5724 KB Output is partially correct
2 Partially correct 2 ms 5724 KB Output is partially correct
3 Partially correct 1 ms 5724 KB Output is partially correct
4 Partially correct 1 ms 5552 KB Output is partially correct
5 Partially correct 1 ms 5724 KB Output is partially correct
6 Correct 1 ms 5724 KB Output is correct
7 Correct 2 ms 5724 KB Output is correct
8 Correct 1 ms 5724 KB Output is correct
9 Correct 2 ms 5724 KB Output is correct
10 Correct 2 ms 5768 KB Output is correct
11 Partially correct 2 ms 5724 KB Output is partially correct
12 Partially correct 2 ms 5720 KB Output is partially correct
13 Partially correct 2 ms 5724 KB Output is partially correct
14 Partially correct 2 ms 5720 KB Output is partially correct
15 Partially correct 2 ms 5724 KB Output is partially correct
16 Partially correct 2 ms 5772 KB Output is partially correct
17 Partially correct 2 ms 5724 KB Output is partially correct
18 Partially correct 2 ms 5724 KB Output is partially correct
19 Partially correct 1 ms 5724 KB Output is partially correct
20 Partially correct 2 ms 5724 KB Output is partially correct
21 Correct 2 ms 5720 KB Output is correct
22 Correct 2 ms 5724 KB Output is correct
23 Correct 1 ms 5724 KB Output is correct
24 Correct 2 ms 5720 KB Output is correct
25 Correct 1 ms 5724 KB Output is correct
26 Partially correct 2 ms 5976 KB Output is partially correct

Subtask #3
9.9 / 33.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 5724 KB Output is partially correct
2 Partially correct 2 ms 5724 KB Output is partially correct
3 Partially correct 1 ms 5724 KB Output is partially correct
4 Partially correct 1 ms 5552 KB Output is partially correct
5 Partially correct 1 ms 5724 KB Output is partially correct
6 Correct 1 ms 5724 KB Output is correct
7 Correct 2 ms 5724 KB Output is correct
8 Correct 1 ms 5724 KB Output is correct
9 Correct 2 ms 5724 KB Output is correct
10 Correct 2 ms 5768 KB Output is correct
11 Partially correct 2 ms 5724 KB Output is partially correct
12 Partially correct 2 ms 5720 KB Output is partially correct
13 Partially correct 2 ms 5724 KB Output is partially correct
14 Partially correct 2 ms 5720 KB Output is partially correct
15 Partially correct 2 ms 5724 KB Output is partially correct
16 Partially correct 2 ms 5772 KB Output is partially correct
17 Partially correct 2 ms 5724 KB Output is partially correct
18 Partially correct 2 ms 5724 KB Output is partially correct
19 Partially correct 1 ms 5724 KB Output is partially correct
20 Partially correct 2 ms 5724 KB Output is partially correct
21 Correct 2 ms 5720 KB Output is correct
22 Correct 2 ms 5724 KB Output is correct
23 Correct 1 ms 5724 KB Output is correct
24 Correct 2 ms 5720 KB Output is correct
25 Correct 1 ms 5724 KB Output is correct
26 Partially correct 2 ms 5976 KB Output is partially correct
27 Partially correct 77 ms 12108 KB Output is partially correct
28 Partially correct 64 ms 11296 KB Output is partially correct
29 Partially correct 48 ms 10324 KB Output is partially correct
30 Partially correct 72 ms 11868 KB Output is partially correct
31 Partially correct 55 ms 10772 KB Output is partially correct
32 Partially correct 64 ms 13584 KB Output is partially correct
33 Partially correct 6 ms 6036 KB Output is partially correct
34 Partially correct 5 ms 5980 KB Output is partially correct
35 Partially correct 12 ms 7264 KB Output is partially correct
36 Correct 50 ms 10068 KB Output is correct
37 Correct 73 ms 11552 KB Output is correct
38 Correct 5 ms 5980 KB Output is correct
39 Correct 59 ms 10836 KB Output is correct
40 Correct 1 ms 5724 KB Output is correct
41 Partially correct 1 ms 5724 KB Output is partially correct