oj.uz

답안 #400119

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
400119 2021-05-07T11:29:03 Z teehandsome 다리 (APIO19_bridges) C++11
16 / 100
 981 ms 3884 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define INF 1e9+7
#define all(x) x.begin(),x.end()
using namespace std;
using namespace __gnu_pbds;
using ll=long long;
using pii=pair<int,int>;
using ppi=pair<int,pii>;
using oset=tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>;

template<typename T>
void _print(vector<T> x) {cerr<<"{"; for(auto e:x) cerr<<e<<","; cerr<<"}";}
void _print(pii x) {cerr<<"{"<<x.first<<","<<x.second<<"}";}
template<typename T>
void _print(T x) {cerr<<x;}

void dbg() {cerr<<endl;}
template<typename Head,typename... Tail>
void dbg(Head H,Tail... T) {
    _print(H);
    if(sizeof...(T)) cerr<<",";
    else cerr<<"\"]";
    dbg(T...);
}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:[\"",dbg(__VA_ARGS__)

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int inf=INF;
const int mxn=1e5+10;
int n,m,q;
vector<int> a;
int t[4*mxn];

void build(int v,int tl,int tr) {
    if(tl>tr) return;
    if(tl==tr) t[v]=a[tl];
    else {
        int mid=(tl+tr)/2;
        build(2*v,tl,mid);
        build(2*v+1,mid+1,tr);
        t[v]=min(t[2*v],t[2*v+1]);
    }
}
void update(int v,int tl,int tr,int pos,int val) {
    assert(pos<m and pos>=0);
    if(tl>tr or tl>pos or tr<pos) return;
    if(tl==tr and tl==pos) t[v]=val;
    else {
        int mid=(tl+tr)/2;
        update(2*v,tl,mid,pos,val);
        update(2*v+1,mid+1,tr,pos,val);
        t[v]=min(t[2*v],t[2*v+1]);
    }
}

int query(int v,int tl,int tr,int l,int r) {
    assert(l<=r);
    if(tl>tr or tl>r or tr<l) return inf;
    if(tl>=l and tr<=r) return t[v];
    int mid=(tl+tr)/2;
    int res=inf;
    res=min(res,query(2*v,tl,mid,l,r));
    res=min(res,query(2*v+1,mid+1,tr,l,r));
    return res;
}

//void deebug(int v,int tl,int tr) {
//    if(v==1) cout<<"======="<<endl;
//    cout<<"["<<v<<", {"<<tl<<","<<tr<<"}]: ";
//    cout<<t[v]<<endl;
//    if(tl==tr) return;
//    int mid=(tl+tr)/2;
//    deebug(2*v,tl,mid);
//    deebug(2*v+1,mid+1,tr);
//}

int f(int l,int r) {
    if(r-2>=m or l-1>=m) return 0;
    if(l<0 or r<0) return 0;
    if(l-1>r-2) return 0;
    return query(1,0,m-1,l-1,r-2);
}

int main () {
    ios::sync_with_stdio(false); cin.tie(0);

    cin>>n>>m; a.resize(m+1);
    for(int i=0;i<m;i++) {
        int u,v; cin>>u>>v;
        cin>>a[i];
    }
    build(1,0,m-1);

    int q; cin>>q;
    while(q--) {
        int t,x,y; cin>>t>>x>>y;
        if(t==1) {
            update(1,0,m-1,x-1,y);
        }
        else {
            int ansL=x,ansR=x;
            int l=1,r=x-1;
            while(l<=r) {
                int mid=(l+r)/2;
                if(f(mid,x)>=y) {
                    ansL=mid; r=mid-1;
                }
                else l=mid+1;
            }
            l=x+1,r=n;
            while(l<=r) {
                int mid=(l+r)/2;
                if(f(x,mid)>=y) {
                    ansR=mid; l=mid+1;
                }
                else r=mid-1;
            }
            cout<<(ansR-ansL+1)<<endl;
        }
    }
}

Subtask #1
0 / 13.0

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

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 468 ms 1108 KB Output is correct
2 Correct 478 ms 1072 KB Output is correct
3 Correct 473 ms 1348 KB Output is correct
4 Correct 507 ms 1044 KB Output is correct
5 Correct 482 ms 1200 KB Output is correct
6 Correct 544 ms 1324 KB Output is correct
7 Correct 533 ms 1216 KB Output is correct
8 Correct 533 ms 1344 KB Output is correct
9 Correct 34 ms 1860 KB Output is correct
10 Correct 490 ms 3068 KB Output is correct
11 Correct 490 ms 2788 KB Output is correct
12 Correct 932 ms 3884 KB Output is correct
13 Correct 183 ms 3836 KB Output is correct

Subtask #3
0 / 17.0

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

Subtask #4
0 / 14.0

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

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 468 ms 1108 KB Output is correct
2 Correct 478 ms 1072 KB Output is correct
3 Correct 473 ms 1348 KB Output is correct
4 Correct 507 ms 1044 KB Output is correct
5 Correct 482 ms 1200 KB Output is correct
6 Correct 544 ms 1324 KB Output is correct
7 Correct 533 ms 1216 KB Output is correct
8 Correct 533 ms 1344 KB Output is correct
9 Correct 34 ms 1860 KB Output is correct
10 Correct 490 ms 3068 KB Output is correct
11 Correct 490 ms 2788 KB Output is correct
12 Correct 932 ms 3884 KB Output is correct
13 Correct 183 ms 3836 KB Output is correct
14 Incorrect 422 ms 788 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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