oj.uz

Submission #116901

# Submission time Handle Problem Language Result Execution time Memory
116901 2019-06-14T04:02:20 Z manh9203 Doktor (COCI17_doktor) C++17
100 / 100
 767 ms 63844 KB 
#include<bits/stdc++.h>
using namespace std;
struct change{
	long l,r,mid,val;
};
bool cmp(change a,change b){
	return a.r-a.l < b.r-b.l;
}
int n,a[500005],ansL,ansR,mx=-1;
long dem[500005][3],cnt[500005];
vector<change> pos;
map<pair<long,long>,bool> check;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]==i){
			cnt[i]=cnt[i-1]+1;
		}else{
			cnt[i]=cnt[i-1];
		}
	}
	for(int i=1;i<=n;i++){
		if(a[i]!=i){
			long l=min(a[i],i);
			long r=max(a[i],i);
			if(check[make_pair(l,r)]==0){
				if(a[l]==r&&a[r]==l){
					pos.push_back({l,r,(l+r)/2,2});
				}else{
					pos.push_back({l,r,(l+r)/2,1});
				}
				check[make_pair(l,r)]=1;
			}
		}
	}
	sort(pos.begin(),pos.end(),cmp);
	ansL=ansR=1;
	for(int i=0;i<pos.size();i++){
		//cout<<pos[i].l<<" "<<pos[i].r<<" "<<pos[i].mid<<" "<<pos[i].val<<endl;
		if((pos[i].r-pos[i].l)%2==1){
			dem[pos[i].mid][0]+=pos[i].val;
			if(cnt[n]+dem[pos[i].mid][0]-(cnt[pos[i].r]-cnt[pos[i].l-1])>mx){
				mx=cnt[n]+dem[pos[i].mid][0]-(cnt[pos[i].r]-cnt[pos[i].l-1]);
				ansL=a[pos[i].l];
				ansR=a[pos[i].r];
			}
		}else{
			dem[pos[i].mid][1]+=pos[i].val;
			if(cnt[n]+dem[pos[i].mid][1]-(cnt[pos[i].r]-cnt[pos[i].l-1])+cnt[pos[i].mid]-cnt[pos[i].mid-1]>mx){
				mx=cnt[n]+dem[pos[i].mid][1]-(cnt[pos[i].r]-cnt[pos[i].l-1])+cnt[pos[i].mid]-cnt[pos[i].mid-1];
				ansL=a[pos[i].l];
				ansR=a[pos[i].r];
			}
		}
	}
	cout<<ansL<<" "<<ansR;
}

Compilation message

doktor.cpp: In function 'int main()':
doktor.cpp:39:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<pos.size();i++){
              ~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 640 KB Output is correct
2 Correct 3 ms 512 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 896 KB Output is correct
2 Correct 4 ms 768 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 640 KB Output is correct
2 Correct 2 ms 384 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1628 KB Output is correct
2 Correct 207 ms 20332 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 11996 KB Output is correct
2 Correct 62 ms 6248 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 767 ms 63844 KB Output is correct
2 Correct 361 ms 29776 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 422 ms 37500 KB Output is correct
2 Correct 165 ms 6008 KB Output is correct