Submission #862520

#	Time	Username	Problem	Language	Result	Execution time	Memory
862520		KN200711	Sequence (APIO23_sequence)	C++17	48 / 100	759 ms	101076 KiB

sequence

#include "sequence.h"
# include <bits/stdc++.h>
# define fi first
# define se second
using namespace std;

const int MXN = 5e5;
vector<int> ct[MXN + 1];
int pref[4 * MXN + 10], pref1[4 * MXN + 10], suff[4 * MXN + 10], suff1[4 * MXN + 10], sm1[4 *MXN + 10], sm2[4 *MXN + 10], arr[MXN + 1];

void merge(int c, int a, int b) {
	pref[c] = max(pref[a], sm1[a] + pref[b]);
	pref1[c] = min(pref1[a], sm2[a] + pref1[b]);
	suff[c] = max(suff[b], sm1[b] + suff[a]);
	suff1[c] = min(suff1[a], sm2[b] + suff1[a]);
	sm1[c] = sm1[a] + sm1[b];
	sm2[c] = sm2[a] + sm2[b];
}

void build(int lf, int rg, int nd) {
	if(lf == rg) {
		if(arr[lf] == 0) {
			pref[nd] = pref1[nd] = suff1[nd] = suff[nd] = 0;
			sm1[nd] = 1;
			sm2[nd] = -1;
		}
		else {
			sm1[nd] = sm2[nd] = pref[nd] = suff[nd] = 1;
			pref1[nd] = suff1[nd] = 0;
		}
	} else {
		int mid = (lf + rg) / 2;
		build(lf, mid, 2*nd+1);
		build(mid+1, rg, 2*nd+2);
		merge(nd, 2*nd+1, 2*nd+2);
	}
}

void upd(int lf, int rg, int nd, int pos, int v) {
	if(lf == rg) {
		int v1, v2;
		if(v == 0) {
			v1 = 1;
			v2 = -1;
		} else {
			v1 = v2 = v;
		}
		sm1[nd] = v1;
		sm2[nd] = v2;
		
		pref[nd] = suff[nd] = max(0, v1);
		pref1[nd] = suff1[nd] = min(0, v2);
	} else {
		int mid = (lf + rg) / 2;
		if(pos <= mid) upd(lf, mid, 2*nd+1, pos, v);
		else upd(mid+1, rg, 2*nd+2, pos, v);
		merge(nd, 2*nd+1, 2*nd+2);
	}
}

pair<int, pair<int, int> > qry(int lf, int rg, int nd, int clf, int crg, int v) {
	if(clf > rg || lf > crg) return make_pair(0, make_pair(0, 0));
	if(clf <= lf && rg <= crg) {
		if(v) return make_pair(sm1[nd], make_pair(pref[nd], suff[nd]));
		else return make_pair(sm2[nd], make_pair(pref1[nd], suff1[nd]));
	} else {
		int mid = (lf + rg) / 2;
		pair<int, pair<int, int> > a, b;
		a = qry(lf, mid, 2*nd+1, clf, crg, v);
		b = qry(mid+1, rg, 2*nd+2, clf, crg, v);
		if(v) return make_pair(a.fi + b.fi, make_pair(max(a.se.fi, a.fi + b.se.fi), max(b.se.se, a.se.se + b.fi)));
		else return make_pair(a.fi + b.fi, make_pair(min(a.se.fi, a.fi + b.se.fi), min(b.se.se, a.se.se + b.fi)));
	}
}

int N1;
int fen[500001];
int sm[500001];

void add(int a, int b) {
	while(a <= N1) {
		fen[a] += b;
		a += a&(-a);
	}
}

void ad(int a, int b) {
	while(a <= N1) {
		sm[a] += b;
		a += a&(-a);
	}
}

int qy(int a) {
	int as = 0;
	while(a > 0) {
		as += fen[a];
		a -= a&(-a);
	}
	return as;
}

int qqy(int a) {
	int as = 0;
	while(a > 0) {
		as += sm[a];
		a -= a&(-a);
	}
	return as;
}

bool cek(int a, int b) {
	int d;
	d = qqy(b + 1) - qqy(a);
//	if(a == 0 && b == 8) cout<<"D : "<<a<<" "<<b<<" "<<d.fi<<" "<<d.se.fi<<" "<<d.se.se<<endl;
	int lr = qy(b + 1) - qy(a);
//	if(a == 0 && b == 8) cout<<lr<<endl; 
	if(lr >= abs(d)) return 1;
	else {
		if(d < 0) {
			d += qry(0, N1 - 1, 0, 0, a-1, 1).se.se + qry(0, N1-1, 0, b+1, N1-1, 1).se.fi;
			if(d > 0) d = 0;
		} else {
			d += qry(0, N1-1, 0, 0, a-1, 0).se.se + qry(0, N1-1, 0, b+1, N1-1, 0).se.fi;
			if(d < 0) d = 0;
		}
		if(lr >= abs(d)) return 1;
		else return 0;
	}
	return 0;
}


int sequence(int N, vector<int> A) {
	N1 = N;
	
	map<int, int> mp;
	for(int i=0;i<N;i++) mp[A[i]] = 1;
	int cnt  = 0;
	for(auto p : mp) mp[p.fi] = cnt++;
	for(int i=0;i<N;i++) {
		arr[i] = mp[A[i]];
		if(arr[i] == 0) add(i + 1, 1);
		else ad(i + 1, 1);
		ct[arr[i]].push_back(i);
	}
	
	build(0, N-1, 0);
	int ans = 0;
	for(int i=0;i<cnt;i++) {
		int r = 0;
		for(int k=0;k<ct[i].size();k++) {
		//	cout<<i<<" "<<k<<" "<<r<<endl;
		//	if(i == 1 && r < ct[i].size()) cout<<r<<" "<<cek(ct[i][k], ct[i][r])<<endl;
			while(r < ct[i].size() && cek(ct[i][k], ct[i][r])) {
				r++;
			//	cout<<"r : "<<r<<endl;
			}
			
		//	cout<<"i : "<<i<<" "<<k<<" "<<r<<endl;
			ans = max(ans, r - k);
		}
		for(int d=0;d<ct[i].size();d++) {
			upd(0, N-1, 0, ct[i][d], -1);
			ad(ct[i][d] + 1, -1);
			add(ct[i][d] + 1, -1);
		}
		for(int d=0;d<ct[i+1].size();d++) {
			upd(0, N-1, 0, ct[i+1][d], 0);
			ad(ct[i+1][d] + 1, -1);
			add(ct[i+1][d] + 1, 1);
		}
	//	cout<<qry(0, N-1, 0, 0, N-1, 0).fi<<endl;
	}
	return ans;
}

Compilation message (stderr)

sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:152:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |   for(int k=0;k<ct[i].size();k++) {
      |               ~^~~~~~~~~~~~~
sequence.cpp:155:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |    while(r < ct[i].size() && cek(ct[i][k], ct[i][r])) {
      |          ~~^~~~~~~~~~~~~~
sequence.cpp:163:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |   for(int d=0;d<ct[i].size();d++) {
      |               ~^~~~~~~~~~~~~
sequence.cpp:168:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  168 |   for(int d=0;d<ct[i+1].size();d++) {
      |               ~^~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 17 / 17
• Subtask 3: 7 / 7
• Subtask 4: 0 / 12
• Subtask 5: 13 / 13
• Subtask 6: 0 / 22
• Subtask 7: 0 / 18