oj.uz

Submission #142865

# Submission time Handle Problem Language Result Execution time Memory
142865 2019-08-11T17:10:53 Z Ort Deda (COCI17_deda) C++11
120 / 140
 1000 ms 4756 KB 
#include<bits/stdc++.h>
#define MEM(a, b) memset(a, (b), sizeof(a))
#define ALL(c) (c).begin(),(c).end()
#define ll long long
#define LINF (ll)1e18
#define INF (int)1e9
#define pb push_back
#define mp make_pair
#define MOD 1000000007
#define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define MAX 200050
 
using namespace std;
 
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
int tree[MAX*4];
 
void update(int n, int b, int e, int idx, int val) {
	if (b>e || b>idx || e<idx) return;
 	if (b==e) {
 		tree[n] = val;
 		return;
	}
 	int mid = (b+e)/2;
 	update(n*2,b,mid,idx,val);
 	update(n*2+1,mid+1,e,idx,val);
 	tree[n] = min(tree[n*2],tree[n*2+1]);
}
 
int query(int n, int b, int e, int l, int r) {
	if (l>e || b>r) return INF;
 	if (b>=l && e<=r) return tree[n];
 	int mid = (b+e)/2;
 	return min(query(n*2,b,mid,l,r),query(n*2+1,mid+1,e,l,r));
}
 
int main() {
	IO;
	for(int i=0;i<MAX*4-1;i++) tree[i] = INF;
	int n, q; cin >> n >> q;
	while(q--) {
		char c; int a, b;
		cin >> c >> a >> b;
		if(c=='M') update(1, 0, n-1, b-1, a);	
		else {
			int l = b-1; int h = MAX-1;
			while(l<h) {
				int mid = (l+h)>>1;
				int tr = query(1, 0, n-1, l, mid);
				if(a>=tr) h = mid;
				else l = mid+1;
			}
			if(l+1>=MAX) cout << -1 << "\n";
			else cout << l+1 << "\n";
		}
	}
	return 0;
}

Subtask #1
120.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3448 KB Output is correct
2 Correct 5 ms 3448 KB Output is correct
3 Correct 13 ms 3448 KB Output is correct
4 Execution timed out 1061 ms 4756 KB Time limit exceeded
5 Correct 735 ms 4340 KB Output is correct
6 Correct 870 ms 4524 KB Output is correct
7 Correct 952 ms 4480 KB Output is correct