oj.uz

Submission #974686

# Submission time Handle Problem Language Result Execution time Memory
974686 2024-05-03T16:01:01 Z Abito Bridges (APIO19_bridges) C++17
16 / 100
 607 ms 3920 KB 
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define ppb pop_back
#define ep insert
#define endl '\n'
#define elif else if
#define pow pwr
#define sqrt sqrtt
//#define int long long
#define ll long long
typedef unsigned long long ull;
using namespace std;
const int N=1e5+5;
int n,m,q,w[N],W,seg[4*N+5],idx,val,lx,rx;
int build(int x,int l,int r){
    if (l>r) return INT_MAX;
    if (l==r) return seg[x]=w[l];
    int mid=(l+r)/2;
    return seg[x]=min(build(x*2,l,mid),build(x*2+1,mid+1,r));
}
void edit(int x,int l,int r){
    if (l>r);
    if (l==r){
        seg[x]=val;
        return;
    }
    int mid=(l+r)/2;
    if (idx<=mid) edit(x*2,l,mid);
    else edit(x*2+1,mid+1,r);
    seg[x]=min(seg[x*2],seg[x*2+1]);
}
int query(int x,int l,int r){
    if (l>=lx && r<=rx) return seg[x];
    if (l>rx || r<lx || l>r) return INT_MAX;
    int mid=(l+r)/2;
    return min(query(x*2,l,mid),query(x*2+1,mid+1,r));
}
int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    cin>>n>>m;
    for (int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y>>w[i];
    }
    build(1,1,n-1);
    cin>>q;
    while (q--){
        int t,x,y;
        cin>>t>>x>>y;
        if (t==1){
            idx=x,val=y;
            edit(1,1,n-1);
            continue;
        }
        int ans=1,l=x,r=n-1,mid,z=x-1;
        lx=x;
        while (l<=r){
            rx=mid=(l+r)/2;
            int c=query(1,1,n-1);
            if (c>=y){
                z=mid;
                l=mid+1;
            }else r=mid-1;
        }ans+=(z-x+1);
        rx=x-1;
        l=1,r=x-1,z=x;
        while (l<=r){
            lx=mid=(l+r)/2;
            int c=query(1,1,n-1);
            if (c>=y){
                z=mid;
                r=mid-1;
            }else l=mid+1;
        }ans+=x-z;
        cout<<ans<<endl;
    }
    return 0;
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 2788 KB Output is correct
2 Correct 316 ms 2712 KB Output is correct
3 Correct 311 ms 2644 KB Output is correct
4 Correct 331 ms 2620 KB Output is correct
5 Correct 311 ms 2672 KB Output is correct
6 Correct 370 ms 2984 KB Output is correct
7 Correct 343 ms 2892 KB Output is correct
8 Correct 344 ms 3256 KB Output is correct
9 Correct 22 ms 1884 KB Output is correct
10 Correct 313 ms 2952 KB Output is correct
11 Correct 323 ms 3036 KB Output is correct
12 Correct 607 ms 3920 KB Output is correct
13 Correct 100 ms 3664 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 285 ms 852 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 597 ms 1632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 2788 KB Output is correct
2 Correct 316 ms 2712 KB Output is correct
3 Correct 311 ms 2644 KB Output is correct
4 Correct 331 ms 2620 KB Output is correct
5 Correct 311 ms 2672 KB Output is correct
6 Correct 370 ms 2984 KB Output is correct
7 Correct 343 ms 2892 KB Output is correct
8 Correct 344 ms 3256 KB Output is correct
9 Correct 22 ms 1884 KB Output is correct
10 Correct 313 ms 2952 KB Output is correct
11 Correct 323 ms 3036 KB Output is correct
12 Correct 607 ms 3920 KB Output is correct
13 Correct 100 ms 3664 KB Output is correct
14 Incorrect 285 ms 852 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -