| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 833305 |
2023-08-22T04:22:38 Z |
vjudge1 |
Exam (eJOI20_exam) |
C++17 |
|
3 ms |
788 KB |
#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
exam.cpp: In function 'void solve()':
exam.cpp:42:12: warning: unused variable 'j' [-Wunused-variable]
42 | for(auto j:o_set){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
336 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
336 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
336 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
