Submission #833305

#TimeUsernameProblemLanguageResultExecution timeMemory
833305vjudge1Exam (eJOI20_exam)C++17
0 / 100
3 ms788 KiB
#include<bits/stdc++.h> #define ll long long #define endl "\n" #define fi first #define se second #define pb push_back #define pll pair<long long, long long> #define loop(i,n) for(int i=1;i<=n;i++) #define loop0(i,n) for(int i=0;i<n;i++) using namespace std; //pbds template #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; void solve(){ ll n; cin >> n; ll a[n+5] = {0}; ll b[n+5] = {0}; vector<pair<pair<ll,ll>,ll>> v; map<ll,vector<ll>> m; for(int i=1;i<=n;i++){ cin >> a[i]; } for(int i=1;i<=n;i++){ cin >> b[i]; } ll ans = 0; for(int i=1;i<=n;i++){ v.pb({{a[i],b[i]},i}); } sort(v.begin(),v.end()); ordered_set<ll> o_set; for(auto i:v){ // cout << i.fi.fi << ' ' << i.fi.se << ' ' << ans << endl; // cout << "o_set : "; for(auto j:o_set){ // cout << "DEBUG" << endl; // cout << j << ' '; } // cout << endl; if(m.count(i.fi.fi)){ ll cnt = 1; ll mx = 0; ll idx = 0; ll start = 0; ll end = 0; for(auto j:m[i.fi.fi]){ ll idx1 = o_set.order_of_key(i.se); ll idx2 = o_set.order_of_key(j); ll sel = abs(idx1-idx2); // cout << idx1 << ' ' << idx2 << ' ' << cnt << endl; if(cnt-sel>mx){ idx = cnt; mx = cnt-sel; start = min(i.se,j); end = max(i.se,j); } cnt++; } // cout << "mx : " << mx << endl; if(mx>0){ ordered_set<ll> o_set2; ans += mx; for(auto i:o_set){ if(i<start||i>end){ o_set2.insert(i); } } for(int j=0;j<idx;j++){ // cout << m[i.fi.fi][j] << endl; o_set2.insert(m[i.fi.fi][j]); } o_set = o_set2; // cout << o_set.size() << endl; } } if(i.fi.fi==i.fi.se){ ans++; o_set.insert(i.se); } else{ m[i.fi.se].pb(i.se); } } cout << o_set.size() << endl; // for(auto i:o_set){ // cout << i << ' '; // } // cout << endl; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int tc = 1; // cin >> tc; while(tc--){ solve(); } }

Compilation message (stderr)

exam.cpp: In function 'void solve()':
exam.cpp:42:12: warning: unused variable 'j' [-Wunused-variable]
   42 |   for(auto j:o_set){
      |            ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...