oj.uz

답안 #409354

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
409354 2021-05-20T15:32:09 Z MOUF_MAHMALAT 다리 (APIO19_bridges) C++14
16 / 100
 1191 ms 4816 KB 
#include<bits/stdc++.h>
#define all(s) s.begin(),s.end()
using namespace std;
typedef int ll;
ll n,q,t,edg,x,y,z,a[100009],p[400009],id[100009];
void build(ll d,ll l,ll r)
{
    if(l==r)
        return void(p[d]=a[l]);
    ll m=(l+r)/2,i=d*2;
    build(i,l,m),build(i+1,m+1,r);
    p[d]=min(p[i],p[i+1]);
}
void up(ll d,ll l,ll r)
{
    if(l==r)
        return void(p[d]=y);
    ll m=(l+r)/2,i=d*2;
    if(id[x]<=m)
        up(i,l,m);
    else
        up(i+1,m+1,r);
    p[d]=min(p[i],p[i+1]);
}
ll best(ll d,ll l,ll r,ll s,ll e)
{
    if(l>e||r<s)
        return 2e9;
    if(s<=l&&e>=r)
        return p[d];
    ll m=(l+r)/2,i=d*2;
    return min(best(i,l,m,s,e),best(i+1,m+1,r,s,e));
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>edg;
    n=2*n-1;
    for(ll i=1; i<=edg; i++)
    {
        cin>>x>>y>>z;
        if(x>y)
            swap(x,y);
        a[x*2-1]=2e9;
        a[y*2-1]=2e9;
        a[x*2]=z;
        id[i]=x*2;
    }
    build(1,1,n);
    cin>>q;
    while(q--)
    {
        cin>>t>>x>>y;
        if(t==1)
        {
            up(1,1,n);
            continue;
        }
        ll s,e;
        ll l=0,r=x*2-1,m;
        while(r-l>1)
        {
            m=(l+r)/2;
            if(best(1,1,n,m,x*2-1)>=y)
                r=m;
            else
                l=m;
        }
        s=r;
        l=x*2-1,r=n+1;
        while(r-l>1)
        {
            m=(l+r)/2;
            if(best(1,1,n,x*2-1,m)>=y)
                l=m;
            else
                r=m;
        }
        e=l;
        cout<<(e-s)/2+1<<endl;
    }
    return 0;
}

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 637 ms 3300 KB Output is correct
2 Correct 620 ms 3396 KB Output is correct
3 Correct 613 ms 3308 KB Output is correct
4 Correct 625 ms 3236 KB Output is correct
5 Correct 620 ms 3528 KB Output is correct
6 Correct 687 ms 3448 KB Output is correct
7 Correct 703 ms 3468 KB Output is correct
8 Correct 673 ms 3504 KB Output is correct
9 Correct 191 ms 1856 KB Output is correct
10 Correct 647 ms 3784 KB Output is correct
11 Correct 684 ms 3772 KB Output is correct
12 Correct 1177 ms 4816 KB Output is correct
13 Correct 197 ms 4608 KB Output is correct

Subtask #3
0 / 17.0

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

Subtask #4
0 / 14.0

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

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 637 ms 3300 KB Output is correct
2 Correct 620 ms 3396 KB Output is correct
3 Correct 613 ms 3308 KB Output is correct
4 Correct 625 ms 3236 KB Output is correct
5 Correct 620 ms 3528 KB Output is correct
6 Correct 687 ms 3448 KB Output is correct
7 Correct 703 ms 3468 KB Output is correct
8 Correct 673 ms 3504 KB Output is correct
9 Correct 191 ms 1856 KB Output is correct
10 Correct 647 ms 3784 KB Output is correct
11 Correct 684 ms 3772 KB Output is correct
12 Correct 1177 ms 4816 KB Output is correct
13 Correct 197 ms 4608 KB Output is correct
14 Incorrect 573 ms 1340 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 -