oj.uz

답안 #249375

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
249375 2020-07-14T18:41:54 Z tc_abd 다리 (APIO19_bridges) C++14
16 / 100
 755 ms 4984 KB 
#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define It it=se.begin();it!=se.end();it++
#define mem(dp,i) memset(dp,i,sizeof(dp))
#define all(x) begin(x),end(x)
#define unmap unordered_map
#define pii pair<int,int>
#include <bits/stdc++.h>
#define pll pair<ll,ll>
#define vll vector<ll>
#define vi vector<int>
#define ld long double
#define ll long long
#define pb push_back
#define sh short int
#define mid (l+r)/2
#define S second
#define F first
#define sqr 447
using namespace std;
const ll inf = 1e18;
const int mod = 1e9+7;
const ld pai=acos(-1);
ll n,m,q;
ll w[50009];
ll tree[200009];
void build(ll node,ll l,ll r){
    if(l == r) return void(tree[node]=w[l]);
    build(node*2,l,mid),build(node*2+1,mid+1,r);
    tree[node] = min(tree[node*2],tree[node*2+1]);
}
void upd(ll node,ll l,ll r,ll k,ll val){
    if(l == r) return void(tree[node]=val);
    if(k <= mid) upd(node*2,l,mid,k,val);
    else upd(node*2+1,mid+1,r,k,val);
    tree[node] = min(tree[node*2],tree[node*2+1]);
}
ll query(ll node,ll l,ll r,ll s,ll e){
    if(s <= l && e >= r) return tree[node];
    if(s <= mid && e > mid){
        return min(query(node*2,l,mid,s,e),query(node*2+1,mid+1,r,s,e));
    }
    if(s <= mid) return query(node*2,l,mid,s,e);
    return query(node*2+1,mid+1,r,s,e);
}
ll bin1(ll node,ll val){
    ll l = node,r = n;
    while(r-l > 1){
        assert(node <= mid-1 && mid-1 <= n-2);
        if(query(1,0,n-2,node,mid-1) >= val) l = mid;
        else r = mid;
    }
    return l-node;
}
ll bin2(ll node,ll val){
    ll l = -1,r = node;
    while(r-l > 1){
        assert(mid <= node-1 && node-1 >= 0);
        if(query(1,0,n-2,mid,node-1) >= val) r = mid;
        else l = mid;
    }
    return node-r;
}
int main(){
    fast,cin>>n>>m;
    for(int i=0;i<m;i++){
        ll a,b,c;
        cin>>a>>b>>c;
        w[i] = c;
    }
    if ( n == 1 ) {
            cin >> q ;
        while ( q -- ){
            int t , a , b ;
            cin >> t >> a >> b ;
            a -- , b -- ;
            if ( t != 1 ) cout << 1 << endl ;
        }exit (0) ;
    }
    build(1,0,n-2);
    cin>>q;
    while(q--){
        ll t,a,b;
        cin>>t>>a>>b;
        if(t == 1) upd(1,0,n-2,a-1,b);
        else cout<<bin1(a-1,b)+bin2(a-1,b)+1<<endl;
    }
}

Subtask #1
0 / 13.0

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

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 435 ms 4728 KB Output is correct
2 Correct 421 ms 4600 KB Output is correct
3 Correct 420 ms 4600 KB Output is correct
4 Correct 423 ms 4728 KB Output is correct
5 Correct 416 ms 4600 KB Output is correct
6 Correct 455 ms 4600 KB Output is correct
7 Correct 443 ms 4600 KB Output is correct
8 Correct 441 ms 4728 KB Output is correct
9 Correct 215 ms 1920 KB Output is correct
10 Correct 445 ms 3576 KB Output is correct
11 Correct 428 ms 3576 KB Output is correct
12 Correct 755 ms 4984 KB Output is correct
13 Correct 143 ms 4600 KB Output is correct

Subtask #3
0 / 17.0

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

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 19 ms 2560 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 435 ms 4728 KB Output is correct
2 Correct 421 ms 4600 KB Output is correct
3 Correct 420 ms 4600 KB Output is correct
4 Correct 423 ms 4728 KB Output is correct
5 Correct 416 ms 4600 KB Output is correct
6 Correct 455 ms 4600 KB Output is correct
7 Correct 443 ms 4600 KB Output is correct
8 Correct 441 ms 4728 KB Output is correct
9 Correct 215 ms 1920 KB Output is correct
10 Correct 445 ms 3576 KB Output is correct
11 Correct 428 ms 3576 KB Output is correct
12 Correct 755 ms 4984 KB Output is correct
13 Correct 143 ms 4600 KB Output is correct
14 Incorrect 392 ms 3576 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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