Submission #142864

#TimeUsernameProblemLanguageResultExecution timeMemory
142864OrtDeda (COCI17_deda)C++11
20 / 140
1068 ms3576 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...