Submission #166919

#	Time	Username	Problem	Language	Result	Execution time	Memory
166919		theStaticMind	Port Facility (JOI17_port_facility)	C++14	0 / 100	6071 ms	292372 KiB

port_facility

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
#define int long long int
using namespace std;
vector<ii>arr;
map<vector<int>,map<vector<int>,map<int,int>>> Q;
int dp(vector<int>A,vector<int>B,int ind){
      if(ind==arr.size())return 1;
      if(Q[A][B].count(ind))return Q[A][B][ind];
      int cnt=0;
      if(arr[ind].second==0){
            if(!A.empty()&&A.back()==arr[ind].first){
                  A.pop_back();
                  return Q[A][B][ind]=dp(A,B,ind+1);
            }
            else if(!B.empty()&&B.back()==arr[ind].first){
                  B.pop_back();
                  return Q[A][B][ind]=dp(A,B,ind+1);
            }
            else assert(0);
      }
      if(A.empty()||A.back()>arr[ind].second){
            A.pb(arr[ind].second);
            cnt=(cnt+dp(A,B,ind+1))%modulo;
            A.pop_back();
      }
      if(B.empty()||B.back()>arr[ind].second){
            B.pb(arr[ind].second);
            cnt=(cnt+dp(A,B,ind+1))%modulo;
            B.pop_back();
      }
      return Q[A][B][ind]=cnt;
}
int32_t main(){
      ios_base::sync_with_stdio(false);
      cin.tie(NULL);
   //   freopen("q.gir","r",stdin);
   //   freopen("q.cik","w",stdout);
      int n,ans=1;
      cin>>n;
      for(int i=0;i<n;i++){
            int a,b;
            cin>>a>>b;
            arr.pb({a,b});
            arr.pb({b,0});
      }
      sort(all(arr));
      vector<int>A,B;
      cout<<dp(A,B,0);
}

Compilation message (stderr)

port_facility.cpp: In function 'long long int dp(std::vector<long long int>, std::vector<long long int>, long long int)':
port_facility.cpp:14:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if(ind==arr.size())return 1;
          ~~~^~~~~~~~~~~~
port_facility.cpp: In function 'int32_t main()':
port_facility.cpp:45:13: warning: unused variable 'ans' [-Wunused-variable]
       int n,ans=1;
             ^~~

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