Submission #713541

#	Time	Username	Problem	Language	Result	Execution time	Memory
713541		bin9638	Bridges (APIO19_bridges)	C++17	0 / 100	285 ms	32908 KiB

bridges

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define N 100010
#define ii pair<int,int>
#define fs first
#define sc second
#define ld double

struct canh
{
    int u,v,L;

    bool operator<(const canh&A)const
    {
        return L>A.L;
    }
}edge[N];

struct truyvan
{
    int type,id,val;
}tv[N];

int n,m,q;
map<int,int>mp[N];

struct BIT
{
    vector<int>lis[N],bit[N];

    void init()
    {
        for(int i=1;i<=n;i++)
        {
            sort(lis[i].begin(),lis[i].end());
            lis[i].erase(unique(lis[i].begin(),lis[i].end()),lis[i].end());
            bit[i].resize(lis[i].size()+1,0);
        }
    }

    void update(int u,int v,int val)
    {
        v=lower_bound(lis[u].begin(),lis[u].end(),v)-lis[u].begin()+1;
      //  cout<<u<<" "<<v<<" "<<val<<endl;
        for(;v>0;v-=v&(-v))
            bit[u][v]+=val;
    }
    int get(int u,int v)
    {
        if(lis[u].empty()||lis[u].back()<v)
            return 0;
        int res=0;
        v=lower_bound(lis[u].begin(),lis[u].end(),v)-lis[u].begin()+1;
        for(;v<=lis[u].size();v+=v&(-v))
            res+=bit[u][v];
        return res;
    }
}BIT;

void update(int u,int val)
{
    while(u!=1)
    {
        BIT.lis[u].pb(val);
        u=u/2;
    }
}

void build(int u,int val)
{
    int L=1e9;
    while(u!=1)
    {
        L=min(L,mp[u/2][u]);
        u=u/2;
        //cout<<u<<" "<<L<<endl;
        BIT.update(u,L,val);
    }
}

int main()
{
    #ifdef SKY
    freopen("A.inp","r",stdin);
    freopen("A.out","w",stdout);
    #endif // SKY
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>edge[i].u>>edge[i].v>>edge[i].L;
        if(edge[i].u>edge[i].v)
            swap(edge[i].u,edge[i].v);
        update(edge[i].u,edge[i].L);
        mp[edge[i].u][edge[i].v]=edge[i].L;
    }
    cin>>q;
    for(int i=1;i<=q;i++)
    {
        cin>>tv[i].type>>tv[i].id>>tv[i].val;
        if(tv[i].type==1)
        {
            update(edge[tv[i].id].u,tv[i].val);
        }
    }
    BIT.init();
    for(int i=1;i<=n;i++)
        build(i,1);
  //  return 0;
    for(int i=1;i<=q;i++)
    {
        //cin>>tv[i].type>>tv[i].id>>tv[i].val;
        if(tv[i].type==1)
        {
            build(edge[tv[i].id].v,-1);
            mp[edge[tv[i].id].u][edge[tv[i].id].v]=tv[i].val;
            build(edge[tv[i].id].v,1);
        }else
        {
            int u=tv[i].id,val=tv[i].val;
            while(u!=1&&mp[u/2][u]>=val)
            {
             //   cout<<u/2<<" "<<u<<" "<<mp[u/2][u]<<endl;
                u=u/2;
            }
           // cout<<u<<endl;
            cout<<(BIT.get(u,val)+1)<<"\n";
        }
    }
    return 0;
}

Compilation message (stderr)

bridges.cpp: In member function 'int BIT::get(int, int)':
bridges.cpp:58:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         for(;v<=lis[u].size();v+=v&(-v))
      |              ~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27