| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 833331 |
2023-08-22T04:36:18 Z |
vjudge1 |
Exam (eJOI20_exam) |
C++14 |
|
139 ms |
1168 KB |
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
vector<int> a(n+2),b(n+2),c(n+2);
map<int,vector<int>> loc;
map<int,int> mp;
priority_queue<int> pq;
for(int i=1;i<=n;i++){
cin>>a[i];
loc[a[i]].push_back(i);
}
for(int i=1;i<=n;i++){
cin>>b[i];
mp[b[i]]++;
if(mp[b[i]]==1)pq.push(-b[i]);
}
while(!pq.empty()){
int x=-pq.top();
pq.pop();
if(loc.find(x)==loc.end())continue;
int first=loc[x][0];
vector<int> tmp_x(n+2),tmp_o(n+2);
vector<int> prefix_x(n+2),suffix_x(n+2);
vector<int> prefix_o(n+2),suffix_o(n+2);
for(int i=1;i<=n;i++){
if(b[i]==x){
tmp_x[i]=1;
}
if(a[i]==b[i]){
tmp_o[i]=1;
}
}
prefix_x[1]=tmp_x[1];
prefix_o[1]=tmp_o[1];
for(int i=2;i<=n;i++){
prefix_x[i]+=prefix_x[i-1]+tmp_x[i];
prefix_o[i]+=prefix_o[i-1]+tmp_o[i];
}
suffix_x[n]=tmp_x[n];
suffix_o[n]=tmp_o[n];
for(int i=n-1;1<=i;i--){
suffix_x[i]+=suffix_x[i+1]+tmp_x[i];
suffix_o[i]+=suffix_o[i+1]+tmp_o[i];
}
//kiri ke kanan
for(int k=0;k<loc[x].size();k++){
/*
1. mentok ke tembok
perlu biggest (prefix+suffix)
2. mentok angka lebih besar
perlu biggest (prefix+suffix) ,dan
perlu dari i selanjutnya (kalo ada) untuk cek kebelakang
lalu perlu biggest (prefix+suffix)
3. ketemu angka x di titik selanjutnya
perlu biggest subarray
loop dari loc[x][i] sampai ada salah satu dari tiga
*/
int type=1;
for(int jj=loc[x][k]+1; jj<=n; jj++){
if(a[jj]==x){
type=3;
}else if(a[jj]>x){
type=2;
}
}
if(type==1){
/*
prefix_x[j] - prefix_x[left-1] + suffix[j+1]
*/
int left=loc[x][k];
int ans=0,right;
for(int j=left; j<=n; j++){
int tmp=prefix_x[j] - prefix_x[left-1] + suffix_o[j+1];
if(ans<tmp){
ans=tmp;
right=j;
}
}
for(int i=left+1;i<=right;i++){
a[i]=x;
}
}else if(type==2){
int left,right;
left=loc[x][k];
for(int i=left;i<=n;i++){
if(a[i]>x){
right=i;
break;
}
}
// prefix[i] - prefix[left-1] + suffix[i+1] - suffix[right+1]
int tmp_right,ans=0;
for(int i=left; i<right; i++){
int tmp=prefix_x[i] - prefix_x[left-1] + suffix_o[i+1] - suffix_o[right+1];
if(ans<tmp){
ans=tmp;
tmp_right=i;
}
}
for(int i=left; i<=tmp_right; i++){
a[i]=x;
}
if(k+1==n)continue;
right=loc[x][k+1];
for(int i=right; 1<=i;i--){
if(a[i]>x){
left=i;
break;
}
}
int tmp_left;
ans=0;
for(int i=right; left<i;i--){
int tmp = prefix_o[i-1] - prefix_o[left-1] + suffix_x[i]-suffix_x[right+1];
if(ans<tmp){
ans=tmp;
tmp_left=i;
}
}
for(int i=right; tmp_left<=i; i--){
a[i]=x;
}
}else if(type==3){
vector<int> sub(n+2);
int left=loc[x][k], right= loc[x][k+1];
int ct=0;
for(int i=left ; i<=right; i++){
if(b[i]==x){
ct++;
sub[i]=-1;
}else if(b[i]==a[i]){
sub[i]=1;
}
}
if(ct==0)continue;
int sum=0;
int tmp_left=left,tmp_right=left;
int ll,rr;
int ans=0;
for(int i=left; i<=right; i++){
sum+=sub[i];
if(ans<sum){
ans=sum;
ll=tmp_left;
rr=tmp_right;
}
if(sum<0){
sum=0;
tmp_left=tmp_right=i;
}
}
for(int i=left; i<ll ;i++){
a[i]=x;
}
for(int i=right; rr<i ;i--){
a[i]=x;
}
}
}
//[0] ke kanan
int right=loc[x][0],left;
int tmp_ans=0,tmp;
for(int i=right ; 1<=i; i--){
if(a[i]>x)break;
tmp=prefix_o[i-1] + suffix_x[i] - suffix_x[right+1];
if(tmp_ans<tmp){
tmp_ans=tmp;
left=i;
}
}
for(int i=right; left<=i; i--){
a[i]=x;
}
}
int ans=0;
for(int i=1;i<=n;i++){
if(a[i]==b[i])ans++;
}
// for(int i=1;i<=n;i++){
// cout<<a[i]<<" ";
// }
// cout<<"\n";
cout<<ans<<"\n";
return 0;
}
Compilation message
exam.cpp: In function 'int main()':
exam.cpp:59:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for(int k=0;k<loc[x].size();k++){
| ~^~~~~~~~~~~~~~
exam.cpp:29:7: warning: unused variable 'first' [-Wunused-variable]
29 | int first=loc[x][0];
| ^~~~~
exam.cpp:195:23: warning: 'left' may be used uninitialized in this function [-Wmaybe-uninitialized]
195 | int right=loc[x][0],left;
| ^~~~
exam.cpp:169:12: warning: 'rr' may be used uninitialized in this function [-Wmaybe-uninitialized]
169 | int ll,rr;
| ^~
exam.cpp:169:9: warning: 'll' may be used uninitialized in this function [-Wmaybe-uninitialized]
169 | int ll,rr;
| ^~
exam.cpp:149:30: warning: 'tmp_left' may be used uninitialized in this function [-Wmaybe-uninitialized]
149 | for(int i=right; tmp_left<=i; i--){
| ~~~~~~~~^~~
exam.cpp:118:9: warning: 'tmp_right' may be used uninitialized in this function [-Wmaybe-uninitialized]
118 | int tmp_right,ans=0;
| ^~~~~~~~~
exam.cpp:119:22: warning: 'right' may be used uninitialized in this function [-Wmaybe-uninitialized]
119 | for(int i=left; i<right; i++){
| ~^~~~~~
exam.cpp:101:23: warning: 'right' may be used uninitialized in this function [-Wmaybe-uninitialized]
101 | for(int i=left+1;i<=right;i++){
| ~^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
34 ms |
1156 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
388 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
139 ms |
1168 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
