oj.uz

Submission #142864

# Submission time Handle Problem Language Result Execution time Memory
142864 2019-08-11T17:06:51 Z Ort Deda (COCI17_deda) C++11
20 / 140
 1000 ms 3576 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-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
20.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Incorrect 3 ms 1144 KB Output isn't correct
3 Incorrect 11 ms 1144 KB Output isn't correct
4 Execution timed out 1068 ms 3312 KB Time limit exceeded
5 Incorrect 777 ms 2272 KB Output isn't correct
6 Incorrect 905 ms 3396 KB Output isn't correct
7 Incorrect 957 ms 3576 KB Output isn't correct