제출 #1228439

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1228439		vako_p	서열 (APIO23_sequence)	C++20	0 / 100	2099 ms	76380 KiB

sequence

#include "sequence.h"
#include <bits/stdc++.h> 
using namespace std;
#define ll int
#define pb push_back
#define ff first
#define sd second
#define debug(x) cerr << #x << "----> " << x << endl;
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")

const int mxN = 5e5 + 5;
ll n,a[mxN];

struct segtree{
	vector<ll> mn,mx,v1,b;
	ll sz = 1,inf = 1e9;
	
	void init(){
		while(sz < n + 5) sz *= 2;
		v1.assign(2 * sz, 0LL);
		mn.assign(2 * sz, 0LL);
		mx.assign(2 * sz, 0LL);
		b.assign(n + 5, 0LL);
	}
	
	void f(ll x){
		mx[x] += v1[x];
		mn[x] += v1[x];
		if(x < sz - 1){
			v1[2 * x + 1] += v1[x];
			v1[2 * x + 2] += v1[x];
		}
		v1[x] = 0;
	}
	
	void set(ll val, ll l, ll r, ll x, ll lx, ll rx){
		f(x);
		if(lx >= r or rx <= l) return;
		if(lx >= l and rx <= r){
			v1[x] += val;
			f(x);
			return;
		}
		ll mid = lx + (rx - lx) / 2;
		set(val, l, r, 2 * x + 1, lx, mid);
		set(val, l, r, 2 * x + 2, mid, rx);
		mx[x] = max(mx[2 * x + 1], mx[2 * x + 2]);
		mn[x] = min(mn[2 * x + 1], mn[2 * x + 2]);
	}
	
	void set(ll val, ll i){
		set(val - b[i], i, n + 1, 0, 0, sz);
		b[i] = val;
	}
	
	pair<ll,ll> find(ll l, ll r, ll x, ll lx, ll rx){
		f(x);
		if(lx >= r or rx <= l) return {1e9, -1e9};
		if(lx >= l and rx <= r) return {mn[x], mx[x]};
		ll mid = lx + (rx - lx) / 2;
		pair<ll,ll> k = find(l, r, 2 * x + 1, lx, mid),k1 = find(l, r, 2 * x + 2, mid, rx);
		return {min(k.ff, k1.ff), max(k.sd, k1.sd)};
	}
	
	pair<ll,ll> find(ll l, ll r){
		return find(l, r, 0, 0, sz);
	}
};

int sequence(int N, std::vector<int> A) {
  	n = N;
  	for(int i = 1; i <= n; i++) a[i] = A[i - 1];
  	segtree s,s1,s2;
	s.init();
	s1.init();
	s2.init();
	vector<ll> v[n + 1];
	for(int i = 1; i <= n; i++){
		v[a[i]].pb(i);
		s.set(1, i);
		s1.set(1, i);
		s2.set(1, i);
	}
	ll ans = 1;
	for(int i = 1; i <= n; i++){
		ll r1 = 0;
		vector<ll>& vv = v[i];
		for(auto it : vv){
			s.set(0, it);
			s2.set(-1, it);
		}
//		s.set(-2, 1);
		for(int l1 = 0; l1 < vv.size() and r1 < vv.size(); l1++){
			bool ok = false;
			int l = vv[l1],r = vv[r1];
//			s.set(1, r);
			s2.set(0, r);
			pair<ll,ll> x = s.find(0, l),y = s.find(r, n + 1);
			ll sz = r1 - l1 + 1;
			if(x.sd <= y.sd){
				if(y.ff - sz <= x.sd) ok = true;
				else if(s2.find(r, n + 1).ff - sz <= x.sd) ok = true;
			}
			else{
				if(x.ff - sz <= y.sd) ok = true;
				else if(x.ff - sz <= s1.find(r, n + 1).sd) ok = true;
			}
//		cout << i << ' ' << l << ' ' << r << "(" << ok << ")" << "---> ";
//		for(int i1 = 0; i1 <= n; i1++) cout << s.find(i1, i1 + 1).ff << ' '; cout << '\n';
//			cout << "-----------------. " << x.ff << ' ' << x.sd << ' ' << y.ff << ' ' << y.sd<< '\n';
			r1++;
			if(ok){
				ans = max(ans, r1 - l1);
				l1--;
				continue;
			}
			s.set(0, l);
			s1.set(0, l);
			s2.set(0, l);
		}
		for(auto it : vv){
			s.set(-1, it);
			s1.set(-1, it);
			s2.set(-1, it);
		}
	}
	return ans;
}

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