Submission #749527

#	Time	Username	Problem	Language	Result	Execution time	Memory
749527		penguin133	Sequence (APIO23_sequence)	C++17	69 / 100	2055 ms	282060 KiB

sequence

#include <bits/stdc++.h>
using namespace std;

//#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
struct node{
	int s, e, m;
	int mx, mn, lazy, val;
	node *l, *r;
	node(int _s, int _e){
		s = _s, e = _e, m = (s + e) >> 1;
		if(s != e)l = new node(s, m), r = new node(m+1, e);
		mx = mn = lazy = val = 0;
	}
	
	void prop(){
		if(!lazy)return;
		mx += lazy, mn += lazy;
		if(s != e)l->lazy += lazy, r->lazy += lazy;
		lazy = 0;
	}
	
	void upd(int a, int b, int c){
		if(a == s && b == e)lazy += c;
		else{
			if(b <= m)l->upd(a, b, c);
			else if(a > m)r->upd(a, b, c);
			else l->upd(a, m, c), r->upd(m+1, b, c);
			l->prop(), r->prop();
			mn= min(l->mn, r->mn);
			mx=  max(l->mx, r->mx);
		}
	}
	
	pi qry(int a, int b){
		prop();
		if(a == s && b == e)return {mn, mx};
		if(b <= m)return l->qry(a, b);
		else if(a > m)return r->qry(a, b);
		else{
			pi lft = l->qry(a, m), rgt = r->qry(m+1 ,b);
			return {min(lft.fi, rgt.fi), max(lft.se, rgt.se)};
		}
	}
	
}*lft, *rgt, *lft2, *rgt2;

vector <int> occ[500005];
int sequence(int N, vector <int> A){
	
	for(int i=0;i<N;i++)occ[A[i]].push_back(i);
	lft = new node(0, N - 1);
	rgt = new node(0, N - 1);
	lft2 = new node(0, N - 1);
	rgt2 = new node(0, N - 1);
	int ans = 1;
	for(int i=0;i<N;i++){
		lft->upd(i, N - 1, 1);
		rgt->upd(0, i, 1);
		lft2->upd(i, N - 1, 1);
		rgt2->upd(0, i, 1);
	}
	bool f = 0;
	for(int i=1;i<=N;i++){
		
		for(auto j : occ[i]){
			lft2->upd(j, N - 1, -2);
			rgt2->upd(0, j, -2);
		}
		int in = 0;
		for(int j = 1; j < (int)occ[i].size(); j++){
			int r = occ[i][j];
			while(in < j){
				int l = occ[i][in];
				pi tmp = rgt->qry(0, l), tmp2 = lft->qry(r, N - 1);
				pi ref = rgt->qry(l, l), ref2 = lft->qry(r, r);
				pi tmp3 = rgt2->qry(0, l), tmp4 = lft2->qry(r, N - 1);
				pi ref3 = rgt2->qry(l, l), ref4 = lft2->qry(r, r);
				tmp.fi -= ref.fi; tmp.se -= ref.se; tmp2.fi -= ref2.fi; tmp2.se -= ref2.se;
				tmp.fi += tmp2.fi;
				tmp.se += tmp2.se;
				tmp3.fi -= ref3.fi; tmp3.se -= ref3.se; tmp4.fi -= ref4.fi; tmp4.se -= ref4.se;
				tmp3.fi += tmp4.fi;
				tmp3.se += tmp4.se;
				int val = lft->qry(r, r).fi - (l == 0 ? 0 : lft->qry(l - 1, l - 1).fi);
				int val2 = lft2->qry(r, r).fi - (l == 0 ? 0 : lft2->qry(l - 1, l - 1).fi);
				long long mn = val + tmp.se, mx = val2 + tmp3.fi;
				if(mn * mx > 0)in++;
				else break;
			}
			//cout << i << ' ' << j << ' ' << in << '\n';
			ans = max(ans, j - in + 1);
		}
		for(auto j : occ[i]){
			lft->upd(j, N - 1, -2);
			rgt->upd(0, j, -2);
		}
	}
	return ans;
}

Compilation message (stderr)

sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:70:7: warning: unused variable 'f' [-Wunused-variable]
   70 |  bool f = 0;
      |       ^

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