oj.uz

Submission #142862

# Submission time Handle Problem Language Result Execution time Memory
142862 2019-08-11T16:28:06 Z Ort Deda (COCI17_deda) C++11
60 / 140
 1000 ms 4088 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-1;
				else l = mid+1;
			}
			if(l+1>=MAX) cout << -1 << "\n";
			else cout << l+1 << "\n";
		}
	}
	return 0;
}

Subtask #1
60.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Correct 3 ms 1144 KB Output is correct
3 Correct 11 ms 1144 KB Output is correct
4 Execution timed out 1064 ms 3868 KB Time limit exceeded
5 Incorrect 765 ms 2888 KB Output isn't correct
6 Incorrect 899 ms 4088 KB Output isn't correct
7 Incorrect 960 ms 3844 KB Output isn't correct