# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
962049 |
2024-04-13T05:44:53 Z |
Amr |
Bridges (APIO19_bridges) |
C++17 |
|
667 ms |
8784 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define S second
#define F first
#define all(x) (x).begin(),(x).end()
#define sz size()
#define Yes cout << "YES" << endl
#define No cout << "NO" << endl
#define pb(x) push_back(x);
#define endl '\n'
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const int N=3e5+7;
ll INF=INT_MAX,mod=1e9+7;
int TT=1;
ll power(ll x, unsigned int y)
{
ll res = 1;
x = x; // % mod;
if (x == 0) return 0;
while (y > 0)
{
if (y & 1) res = (res*x) ; // % mod;
y = y>>1;
x = (x*x) ; // % mod;
}
return res;
}
ll seg[N*2];
ll a[N];
ll siz= 1;
ll n , m, q;
ll get(ll l ,ll r , ll x = 0, ll lx = 0, ll rx = siz)
{
if(l==r) return 0;
if(lx>=r||rx<=l) return 1e18;
if(lx>=l&&rx<=r) return seg[x];
ll mid = (lx+rx)/2;
ll s1 = get(l,r,2*x+1,lx,mid);
ll s2 = get(l,r,2*x+2,mid,rx);
return min(s1,s2);
}
void update(ll in, ll val, ll x =0, ll lx = 0, ll rx = siz)
{
if(rx-lx==1)
{
seg[x] = val;
return;
}
ll mid = (lx+rx)/2;
if(in<mid) update(in,val,2*x+1,lx,mid);
else update(in,val,2*x+2,mid,rx);
seg[x] = min(seg[2*x+1],seg[2*x+2]);
}
void build(ll x =0, ll lx = 0, ll rx = siz)
{
if(rx-lx==1)
{
seg[x] = a[lx];
return;
}
ll mid = (lx+rx)/2;
build(2*x+1,lx,mid);
build(2*x+2,mid,rx);
seg[x] = min(seg[2*x+1],seg[2*x+2]);
}
void solve()
{
cin >> n >> m;
for(int i = 1; i <= m; i++)
{
ll x, y; cin >> x >> x >> y;
a[i] = y;
}
siz = 1;
while(siz<=n) siz*=2;
build();
ll q; cin >> q;
while(q--)
{
ll tp, x , y; cin >> tp >> x >> y;
if(tp==1)
{
a[x] = y;
update(x,y);
}
else
{
ll st = x, w = y;
ll l = st, r = n+1;
while(l+1<r)
{
ll mid = (l+r)/2;
if(get(st,mid)>=w) l = mid;
else r = mid;
}
ll r2 = l;
l = 0, r = st;
while(l+1<r)
{
ll mid = (l+r)/2;
if(get(mid,st)>=w) r = mid;
else l = mid;
}
ll r1 = r;
cout << r2-r1+1<< endl;
}
}
}
int main(){
//freopen("friday.in","r",stdin);
//freopen("friday.out","w",stdout);
fast;
while(TT--)
solve();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
2392 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
355 ms |
7300 KB |
Output is correct |
2 |
Correct |
326 ms |
7696 KB |
Output is correct |
3 |
Correct |
342 ms |
7416 KB |
Output is correct |
4 |
Correct |
344 ms |
7544 KB |
Output is correct |
5 |
Correct |
322 ms |
7704 KB |
Output is correct |
6 |
Correct |
415 ms |
7600 KB |
Output is correct |
7 |
Correct |
392 ms |
7504 KB |
Output is correct |
8 |
Correct |
386 ms |
7340 KB |
Output is correct |
9 |
Correct |
22 ms |
4184 KB |
Output is correct |
10 |
Correct |
345 ms |
6500 KB |
Output is correct |
11 |
Correct |
348 ms |
6520 KB |
Output is correct |
12 |
Correct |
639 ms |
7632 KB |
Output is correct |
13 |
Correct |
109 ms |
7448 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
299 ms |
7064 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
667 ms |
8784 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
355 ms |
7300 KB |
Output is correct |
2 |
Correct |
326 ms |
7696 KB |
Output is correct |
3 |
Correct |
342 ms |
7416 KB |
Output is correct |
4 |
Correct |
344 ms |
7544 KB |
Output is correct |
5 |
Correct |
322 ms |
7704 KB |
Output is correct |
6 |
Correct |
415 ms |
7600 KB |
Output is correct |
7 |
Correct |
392 ms |
7504 KB |
Output is correct |
8 |
Correct |
386 ms |
7340 KB |
Output is correct |
9 |
Correct |
22 ms |
4184 KB |
Output is correct |
10 |
Correct |
345 ms |
6500 KB |
Output is correct |
11 |
Correct |
348 ms |
6520 KB |
Output is correct |
12 |
Correct |
639 ms |
7632 KB |
Output is correct |
13 |
Correct |
109 ms |
7448 KB |
Output is correct |
14 |
Incorrect |
299 ms |
7064 KB |
Output isn't correct |
15 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
2392 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |