Submission #1298076

#	Time	Username	Problem	Language	Result	Execution time	Memory
1298076		ender_shayan	Port Facility (JOI17_port_facility)	C++20	78 / 100	97 ms	32440 KiB

port_facility

#include <bits/stdc++.h>

using namespace std;

// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;

typedef long long ll;
typedef long double	ld;
typedef pair<int, int>	pii  ;
typedef pair<ll, ll>	pll  ;
typedef vector<pii>     vii  ;
typedef vector<int>     veci ;
typedef vector<pll>     vll  ;
typedef vector<ll>      vecll;

// find_by_order             order_of_key

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define F		        first
#define S		        second
#define pb		        push_back
#define endl            '\n'
#define Mp		        make_pair
#define all(x)          x.begin(), x.end()
#define debug(x)        cerr << #x << " = " << x << endl
#define set_dec(x)	    cout << fixed << setprecision(x);
#define fast_io         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io         freopen("in.txt" , "r" , stdin) ; freopen("out.txt" , "w" , stdout);
#define lb              lower_bound
#define ub              upper_bound
#define for1(n)         for(int i=1;i<=n;i++)
#define for0(n)         for(int i=0;i<n;i++)
#define forn(n)         for(int i=n;i>0;i--)
#define pq              priority_queue <int, vector<int>, greater<int>>
#define pq2              priority_queue <pair<int,pii>, vector<pair<int,pii>>, greater<pair<int,pii>>>


const ll mod = 1e9+7 ;// 998244353 ;// 1e9+9;

ll inf=1e18;
const int N=2e5+100,L=21,bs=701,NN=1e6;
int E[N],n,m,k,q,is[N];
vector<int>g[N];
bitset<N>iss;
pii A[N];
pq B[N],C[N];
set<pair<int,pii>> D;
ll ans;
pii merg(pii a,pii b,bool o){
    //b->a
    if(B[a.F].size()+C[a.F].size()<B[b.F].size()+C[b.F].size())swap(a,b);

    if(a.S==0)D.erase({C[a.F].top(),{a.F,1}});
    else D.erase({B[a.F].top(),{a.F,0}});

    if(b.S==0)D.erase({C[b.F].top(),{b.F,1}});
    else D.erase({B[b.F].top(),{b.F,0}});

    if(o^a.S^b.S)
        swap(B[b.F],C[b.F]);
    while(B[b.F].size()){
        B[a.F].push(B[b.F].top());
        B[b.F].pop();
    }
    while(C[b.F].size()){
        C[a.F].push(C[b.F].top());
        C[b.F].pop();
    }
    if(a.S!=0)D.insert({B[a.F].top(),{a.F,0}});
    else D.insert({C[a.F].top(),{a.F,1}});
    return a;
}
int main(){
    fast_io
    cin>>n;
    for1(n){
        int x,y;cin>>x>>y;
        is[x]=y;
    }
    for1(n*2){
        if(is[i]==0){
            pair<int,pii>p=(*D.begin());D.erase(D.begin());
            int x=p.S.F,o=p.S.S;
            if(o==0){
                B[x].pop();
                D.insert({B[x].top(),{x,0}});
            }
            else{
                C[x].pop();
                D.insert({C[x].top(),{x,1}});
            }
            continue;
        }
        vector<pair<int,pii>>vec;
        while(D.size() && (*D.begin()).F<is[i]){
            vec.pb((*D.begin()));
            D.erase(D.begin());
        }
        B[i].push(is[i]);B[i].push(mod+i*3);
        C[i].push(mod+i*3+1);
        D.insert({mod+i*3+1,{i,1}});
        pii cand={i,0};iss[i]=1;
        for(pair<int,pii>p:vec){
            if(iss[p.S.F])return cout<<"0\n",0;
            iss[p.S.F]=1;
            cand=merg(cand,p.S,(cand.F==i));
        }
        if(cand.S==0)D.insert({B[cand.F].top(),cand});
        else D.insert({C[cand.F].top(),cand});
        iss[i]=0;
        for(pair<int,pii>p:vec)iss[p.S.F]=0;
    }
    ans=1;
    for1(D.size()/2)ans=ans*2%mod;
    cout<<ans<<endl;



}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:105:26: warning: narrowing conversion of '((((long long int)mod) + ((long long int)(i * 3))) + 1)' from 'long long int' to 'int' [-Wnarrowing]
  105 |         D.insert({mod+i*3+1,{i,1}});
      |                   ~~~~~~~^~

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 56 / 56
• Subtask 4: 0 / 22