oj.uz

답안 #440498

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
440498 2021-07-02T10:34:56 Z den_tar 다리 (APIO19_bridges) C++14
29 / 100
 3000 ms 10416 KB 
#include <bits/stdc++.h>

using namespace std;

#define fast ios_base::sync_with_stdio();cin.tie();cout.tie();
#define en cout<<endl;
#define ops cout<<"ops"<<endl;
#define line cout<<"---------------------------"<<endl;
#define fi first
#define se second

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pllll;
typedef string str;

const ll DIM = 1e5 + 7;
const ll DIMM = 5e4 + 7;
const ll DDIM = 7;
const ll INF = 1e18 + 7;
const ll X = 1e5 + 7;
const ll BS = 2e5 + 7;
const ll AS = 26 + 7;
const ll MODULO = 1e9 + 7;

ll nt,n,m,k,q;

ll fl;

ll val,val1;

ll v1,v2;

ll d[DIM],vis[DIM];

vector<pllll> a[DIM];

ll type,x,y;

ll res;















void clearvis(){
    for(int i=1;i<=n;i++)vis[i]=0;

    return;
}

void dfs(ll v,ll w){

    res++;
    vis[v]=1;

    for(auto to:a[v]){
     if(vis[to.fi]==1 || d[to.se]<w)continue;
     dfs(to.fi,w);
    }

    return;
}

void solve1(){
    cin>>k;

    for(int qq=1;qq<=k;qq++){
     cin>>type>>x>>y;

     if(type==1)d[x]=y;
     else{
      clearvis();
      res=0;
      dfs(x,y);
      cout<<res<<endl;
     }
    }

    return;
}














ll t[4*DIM];

ll l1,r1,l2,r2,mid;


void btree(ll v,ll tl,ll tr){

    if(tl==tr){
     t[v]=d[tl];
     return;
    }

    ll tm=(tl+tr)/2;

    btree(2*v+1,tl,tm);
    btree(2*v+2,tm+1,tr);

    t[v]=min(t[2*v+1],t[2*v+2]);

    return;
}

void up(ll v,ll tl,ll tr,ll p,ll val){

    if(tr<p || p<tl)return;

    if(tl==tr){
     t[v]=val;
     return;
    }

    ll tm=(tl+tr)/2;

    up(2*v+1,tl,tm,p,val);
    up(2*v+2,tm+1,tr,p,val);

    t[v]=min(t[2*v+1],t[2*v+2]);

    return;
}

ll f(ll v,ll tl,ll tr,ll l,ll r){

    if(tr<l || r<tl)return INF;

    if(l<=tl && tr<=r)return t[v];

    ll tm=(tl+tr)/2;

    return min(f(2*v+1,tl,tm,l,r),f(2*v+2,tm+1,tr,l,r));
}

void solve2(){

    btree(0,1,m);

    cin>>k;

    for(int qq=1;qq<=k;qq++){
     cin>>type>>x>>y;

     if(type==1){
      up(0,1,m,x,y);
      d[x]=y;
     }
     else{

      l1=1;r1=x-1;
      while(l1<r1){
       mid=(l1+r1)/2;
       if(f(0,1,m,mid,x-1)<y)l1=mid+1;
       else r1=mid;
      }

      l2=x;r2=m;
      while(l2<r2){
       mid=(l2+r2+1)/2;
       if(f(0,1,m,x,mid)<y)r2=mid-1;
       else l2=mid;
      }

      if(d[l2]>=y)l2++;
      if(d[r1]<y)r1++;

      res=l2-r1+1;

      cout<<res<<endl;
     }
    }
    return;
}


void solve3(){

    cin>>k;

    for(int qq=1;qq<=k;qq++){
     cin>>type>>x>>y;
     cout<<1<<endl;
    }
    return;
}

int main()
{
    fast;
    //ll x1,y1,x2,y2;

    cin>>n>>m;

    if(m!=(n-1))fl=1;

    for(int i=1;i<=m;i++){
     cin>>v1>>v2>>d[i];

     if(v1!=i || v2!=(i+1))fl=1;

     a[v1].push_back({v2,i});
     a[v2].push_back({v1,i});
    }

    if(m==0){
     solve3();
     return 0;
    }

    if(fl==0){
     solve2();
     return 0;
    }

    solve1();

    return 0;
}

/*
8 7
1 2 9
2 3 1
3 4 9
4 5 9
5 6 9
6 7 1
7 8 9
11
2 4 2
2 8 2
2 1 2
1 2 9
2 4 2
2 8 2
2 1 2
1 6 9
2 4 2
2 8 2
2 1 2
*/

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2560 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 54 ms 2764 KB Output is correct
4 Correct 25 ms 2664 KB Output is correct
5 Correct 21 ms 2636 KB Output is correct
6 Correct 20 ms 2636 KB Output is correct
7 Correct 19 ms 2676 KB Output is correct
8 Correct 21 ms 2668 KB Output is correct
9 Correct 19 ms 2668 KB Output is correct
10 Correct 23 ms 2664 KB Output is correct
11 Correct 20 ms 2676 KB Output is correct
12 Correct 20 ms 2672 KB Output is correct
13 Correct 22 ms 2680 KB Output is correct
14 Correct 21 ms 2680 KB Output is correct
15 Correct 22 ms 2636 KB Output is correct
16 Correct 18 ms 2636 KB Output is correct
17 Correct 19 ms 2664 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 679 ms 6508 KB Output is correct
2 Correct 682 ms 9172 KB Output is correct
3 Correct 687 ms 9156 KB Output is correct
4 Correct 702 ms 9336 KB Output is correct
5 Correct 697 ms 9356 KB Output is correct
6 Correct 738 ms 9440 KB Output is correct
7 Correct 751 ms 9200 KB Output is correct
8 Correct 754 ms 9224 KB Output is correct
9 Correct 247 ms 4252 KB Output is correct
10 Correct 668 ms 8156 KB Output is correct
11 Correct 684 ms 8132 KB Output is correct
12 Correct 1151 ms 9352 KB Output is correct
13 Correct 317 ms 9112 KB Output is correct

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1449 ms 5132 KB Output is correct
2 Correct 2413 ms 3404 KB Output is correct
3 Execution timed out 3065 ms 5140 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3067 ms 10416 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 679 ms 6508 KB Output is correct
2 Correct 682 ms 9172 KB Output is correct
3 Correct 687 ms 9156 KB Output is correct
4 Correct 702 ms 9336 KB Output is correct
5 Correct 697 ms 9356 KB Output is correct
6 Correct 738 ms 9440 KB Output is correct
7 Correct 751 ms 9200 KB Output is correct
8 Correct 754 ms 9224 KB Output is correct
9 Correct 247 ms 4252 KB Output is correct
10 Correct 668 ms 8156 KB Output is correct
11 Correct 684 ms 8132 KB Output is correct
12 Correct 1151 ms 9352 KB Output is correct
13 Correct 317 ms 9112 KB Output is correct
14 Correct 1449 ms 5132 KB Output is correct
15 Correct 2413 ms 3404 KB Output is correct
16 Execution timed out 3065 ms 5140 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2560 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 54 ms 2764 KB Output is correct
4 Correct 25 ms 2664 KB Output is correct
5 Correct 21 ms 2636 KB Output is correct
6 Correct 20 ms 2636 KB Output is correct
7 Correct 19 ms 2676 KB Output is correct
8 Correct 21 ms 2668 KB Output is correct
9 Correct 19 ms 2668 KB Output is correct
10 Correct 23 ms 2664 KB Output is correct
11 Correct 20 ms 2676 KB Output is correct
12 Correct 20 ms 2672 KB Output is correct
13 Correct 22 ms 2680 KB Output is correct
14 Correct 21 ms 2680 KB Output is correct
15 Correct 22 ms 2636 KB Output is correct
16 Correct 18 ms 2636 KB Output is correct
17 Correct 19 ms 2664 KB Output is correct
18 Correct 679 ms 6508 KB Output is correct
19 Correct 682 ms 9172 KB Output is correct
20 Correct 687 ms 9156 KB Output is correct
21 Correct 702 ms 9336 KB Output is correct
22 Correct 697 ms 9356 KB Output is correct
23 Correct 738 ms 9440 KB Output is correct
24 Correct 751 ms 9200 KB Output is correct
25 Correct 754 ms 9224 KB Output is correct
26 Correct 247 ms 4252 KB Output is correct
27 Correct 668 ms 8156 KB Output is correct
28 Correct 684 ms 8132 KB Output is correct
29 Correct 1151 ms 9352 KB Output is correct
30 Correct 317 ms 9112 KB Output is correct
31 Correct 1449 ms 5132 KB Output is correct
32 Correct 2413 ms 3404 KB Output is correct
33 Execution timed out 3065 ms 5140 KB Time limit exceeded
34 Halted 0 ms 0 KB -