# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
472973 |
2021-09-14T16:33:56 Z |
_L__ |
Deda (COCI17_deda) |
C++17 |
|
1000 ms |
5092 KB |
// This code is written by _L__
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define F_word ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
typedef long long ll;
typedef long double ld;
const int mod = 1e9+7, N = 2e5+13, inf = 1e9+1;
const ld E = 1e-6;
#define ff first
#define ss second
int t[4*N];
void build(int v, int tl, int tr){
if(tl>tr)return;
if(tl == tr){t[v] = inf; return;}
int tm = (tl+tr)/2;
build(v*2, tl, tm);
build(v*2+1, tm+1, tr);
t[v] = min(t[v*2], t[v*2+1]);
}
void update(int v, int tl, int tr, int idx, int rx){
if(tl > tr) return;
if(tl == tr){t[v] = rx; return;}
int tm = (tl+tr)/2;
if(idx > tm) update(v*2+1, tm+1, tr, idx, rx);
else update(v*2, tl, tm, idx, rx);
t[v] = min(t[v*2], t[v*2+1]);
}
int query(int v, int tl, int tr, int l, int r){
if(tl > tr) return inf;
if(l > tr || r < tl) return inf;
if(tl == l && tr == r) return t[v];
int tm = (tl+tr)/2;
return min(query(v*2, tl, tm, l, min(tm, r)), query(v*2+1, tm+1, tr, max(l, tm+1), r));
}
int lower(int l, int r, int y){
int n = r;
int ans = -1;
while(l<=r){
int mid = (l+r)/2;
int x = query(1,1,n,l,mid);
if(x <= y){
ans = mid;
r = mid-1;
} else l = mid+1;
}
return ans;
}
int main(void){
F_word;
int n, q; cin >> n >> q;
build(1, 1, n);
int a[n] = {};
while(q--){
char c; cin >> c;
if(c == 'M'){
int x; int i; cin >> x >> i;
a[i] = x;
update(1,1,n,i,x);
} else {
int b, y; cin >> y >> b;
int x = lower(b,n,y);
cout << x << endl;
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
10 ms |
400 KB |
Output is correct |
4 |
Execution timed out |
1081 ms |
4660 KB |
Time limit exceeded |
5 |
Correct |
792 ms |
3504 KB |
Output is correct |
6 |
Correct |
941 ms |
4916 KB |
Output is correct |
7 |
Execution timed out |
1068 ms |
5092 KB |
Time limit exceeded |