oj.uz

답안 #721826

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
721826 2023-04-11T07:42:34 Z alvingogo 다리 (APIO19_bridges) C++14
16 / 100
 494 ms 3384 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

struct ST{
    vector<int> st;
    void init(int x){
        st.resize(4*x);
    }
    void update(int v,int L,int R,int p,int k){
        if(L==R){
            st[v]=k;
            return;
        }
        int m=(L+R)/2;
        if(p<=m){
            update(2*v+1,L,m,p,k);
        }
        else{
            update(2*v+2,m+1,R,p,k);
        }
        st[v]=min(st[2*v+1],st[2*v+2]);
    }
    int query(int v,int L,int R,int l,int r){
        if(L==l && r==R){
            return st[v];
        }
        int m=(L+R)/2;
        if(r<=m){
            return query(2*v+1,L,m,l,r);
        }
        else if(l>m){
            return query(2*v+2,m+1,R,l,r);
        }
        else{
            return min(query(2*v+1,L,m,l,m),query(2*v+2,m+1,R,m+1,r));
        }
    }
}st;
int main(){
    AquA;
    int n,m;
    cin >> n >> m;
    st.init(m);
    vector<pair<pair<int,int>,int> > e(m);
    for(int i=0;i<m;i++){
        cin >> e[i].fs.fs >> e[i].fs.sc >> e[i].sc;
        e[i].fs.fs--;
        e[i].fs.sc--;
        st.update(0,0,m-1,i,e[i].sc);
    }
    int q;
    cin >> q;
    for(int i=0;i<q;i++){
        int t;
        cin >> t;
        if(t==1){
            int a,b;
            cin >> a >> b;
            a--;
            st.update(0,0,m-1,a,b);
        }
        else{
            int a,b;
            cin >> a >> b;
            a--;
            int l=0,r=a;
            while(r>l){
                int mid=(l+r)/2;
                if(st.query(0,0,m-1,mid,a-1)>=b){
                    r=mid;
                }
                else{
                    l=mid+1;
                }
            }
            int fl=l;
            l=a-1;
            r=m-1;
            while(r>l){
                int mid=(l+r+1)/2;
                //cout << l << " " << r << " " << mid << '\n';
                if(st.query(0,0,m-1,a,mid)>=b){
                    l=mid;
                }
                else{
                    r=mid-1;
                }
            }
            int fr=l+1;
            cout << fr-fl+1 << "\n";
        }
    }
    return 0;
}

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 247 ms 1888 KB Output is correct
2 Correct 246 ms 1800 KB Output is correct
3 Correct 261 ms 1760 KB Output is correct
4 Correct 254 ms 1700 KB Output is correct
5 Correct 248 ms 1688 KB Output is correct
6 Correct 257 ms 1944 KB Output is correct
7 Correct 276 ms 1860 KB Output is correct
8 Correct 252 ms 1832 KB Output is correct
9 Correct 28 ms 468 KB Output is correct
10 Correct 255 ms 1836 KB Output is correct
11 Correct 244 ms 1772 KB Output is correct
12 Correct 432 ms 2280 KB Output is correct
13 Correct 93 ms 1712 KB Output is correct

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 225 ms 1240 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 494 ms 3384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 247 ms 1888 KB Output is correct
2 Correct 246 ms 1800 KB Output is correct
3 Correct 261 ms 1760 KB Output is correct
4 Correct 254 ms 1700 KB Output is correct
5 Correct 248 ms 1688 KB Output is correct
6 Correct 257 ms 1944 KB Output is correct
7 Correct 276 ms 1860 KB Output is correct
8 Correct 252 ms 1832 KB Output is correct
9 Correct 28 ms 468 KB Output is correct
10 Correct 255 ms 1836 KB Output is correct
11 Correct 244 ms 1772 KB Output is correct
12 Correct 432 ms 2280 KB Output is correct
13 Correct 93 ms 1712 KB Output is correct
14 Incorrect 225 ms 1240 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -