oj.uz

답안 #267098

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
267098 2020-08-15T20:02:39 Z kimbj0709 다리 (APIO19_bridges) C++14
16 / 100
 1059 ms 5660 KB 
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define f first
#define s second
#define maxn 50050
vector<int> seg(maxn*8,INT_MAX);
void update(int node,int start,int end,int pos,int val){
    if(start==end){
        assert(start==pos);
        seg[node] = val;
        return;
    }
    int mid = (start+end)/2;
    if(pos<=mid){
        update(node*2+1,start,mid,pos,val);
    }
    else{
        update(node*2+2,mid+1,end,pos,val);
    }
    seg[node] = min(seg[node*2+1],seg[node*2+2]);
}
int query(int node,int start,int end,int rangemin,int rangemax){
    if(start>rangemax||end<rangemin){
        return INT_MAX;
    }
    if(start>=rangemin&&end<=rangemax){
        return seg[node];
    }
    int mid = (start+end)/2;
    return min(query(node*2+1,start,mid,rangemin,rangemax),query(node*2+2,mid+1,end,rangemin,rangemax));
}
int32_t main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n,m,q;
    int input1,input2,input3;
    cin >> n >> m;
    vector<pair<int,pair<int,int> > > edges;
    for(int i=0;i<m;i++){
        cin >> input1 >> input2 >> input3;
        edges.push_back({input1,{input2,input3}});
        update(0,0,m-1,i,input3);
    }
    cin >> q;
    for(int i=0;i<q;i++){
        cin >> input1 >> input2 >> input3;
        if(input1==1){
            update(0,0,m-1,input2-1,input3);
        }
        else{
            int ans = 1;
            int lo = 0,hi = input2;
            if(lo==hi){
                goto cont1;
            }
            while(lo+1!=hi){
                int mid = (lo+hi)/2;
                assert(input2-2>=mid-1);
                if(query(0,0,m-1,mid-1,input2-2)>=input3){
                    hi = mid;
                }
                else{
                    lo = mid;
                }
            }
            ans += input2-hi;
            //cout << input2-hi << "--\n";
            cont1 : ;
            lo = input2,hi=n+1;
            if(lo==hi){
                goto cont2;
            }
            //cout << lo << " " << hi << endl;
            while(lo+1!=hi){
                int mid = (lo+hi)/2;
                assert(mid-2>=input2-1);
                if(query(0,0,m-1,input2-1,mid-2)>=input3){
                    lo = mid;
                }
                else{
                    hi = mid;
                }
            }
            ans += lo-input2;
            //cout << lo-input2 << "--\n";
            cont2 : ;
            cout << ans << "\n";
        }

    }
}

Subtask #1
0 / 13.0

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

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 486 ms 2840 KB Output is correct
2 Correct 534 ms 2836 KB Output is correct
3 Correct 595 ms 2812 KB Output is correct
4 Correct 470 ms 4256 KB Output is correct
5 Correct 475 ms 5500 KB Output is correct
6 Correct 511 ms 5488 KB Output is correct
7 Correct 756 ms 5488 KB Output is correct
8 Correct 544 ms 5520 KB Output is correct
9 Correct 35 ms 3508 KB Output is correct
10 Correct 470 ms 4464 KB Output is correct
11 Correct 479 ms 4464 KB Output is correct
12 Correct 879 ms 5660 KB Output is correct
13 Correct 175 ms 5396 KB Output is correct

Subtask #3
0 / 17.0

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

Subtask #4
0 / 14.0

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

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 486 ms 2840 KB Output is correct
2 Correct 534 ms 2836 KB Output is correct
3 Correct 595 ms 2812 KB Output is correct
4 Correct 470 ms 4256 KB Output is correct
5 Correct 475 ms 5500 KB Output is correct
6 Correct 511 ms 5488 KB Output is correct
7 Correct 756 ms 5488 KB Output is correct
8 Correct 544 ms 5520 KB Output is correct
9 Correct 35 ms 3508 KB Output is correct
10 Correct 470 ms 4464 KB Output is correct
11 Correct 479 ms 4464 KB Output is correct
12 Correct 879 ms 5660 KB Output is correct
13 Correct 175 ms 5396 KB Output is correct
14 Incorrect 548 ms 2548 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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