Submission #881239

#	Time	Username	Problem	Language	Result	Execution time	Memory
881239		yusuf12360	Sequence (APIO23_sequence)	C++17	28 / 100	2104 ms	58448 KiB

sequence

#include "sequence.h"
#include<bits/stdc++.h>
using namespace std;
const int INF=1e6;
struct node{
	int mn, mx;
	node(int mn=0, int mx=0) : mn(mn), mx(mx) {}
};
int n;
vector<vector<int>> pos;
vector<int> lazy;
vector<node> tr;
void change(int pos, int add) {
	tr[pos].mn+=add;
	tr[pos].mx+=add;
}
node pull(node L, node R) {
	int mn, mx;
	mn=min(L.mn, R.mn);
	mx=max(L.mx, R.mx);
	return node(mn, mx);
}
void push(int pos) {
	lazy[2*pos+1]+=lazy[pos];
	lazy[2*pos+2]+=lazy[pos];
	change(2*pos+1, lazy[pos]);
	change(2*pos+2, lazy[pos]);
	lazy[pos]=0;
}
void update(int ll, int rr=n-1, int add=-1, int pos=0, int l=0, int r=n-1) {
	if(ll>rr) return;
	if(ll==l && rr==r) {change(pos, add); lazy[pos]+=add; return;}
	push(pos); int mid=l+r>>1;
	update(ll, min(rr, mid), add, 2*pos+1, l, mid);
	update(max(mid+1, ll), rr, add, 2*pos+2, mid+1, r);
	tr[pos]=pull(tr[2*pos+1], tr[2*pos+2]);
}
node get(int ll, int rr, int pos=0, int l=0, int r=n-1) {
	if(ll>rr) return node(INF, -INF);
	if(ll==l && rr==r) return tr[pos];
	push(pos); int mid=l+r>>1;
	return pull(get(ll, min(rr, mid), 2*pos+1, l, mid), get(max(mid+1, ll), rr, 2*pos+2, mid+1, r));
}
node build(int pos=0, int l=0, int r=n-1) {
	lazy[pos]=0;
	if(l==r) return tr[pos]=node(l+1, r+1); 
	int mid=l+r>>1;
	return tr[pos]=pull(build(2*pos+1, l, mid), build(2*pos+2, mid+1, r));
}
bool can(int k) {
	build();
	for(int val=1; val<=n; val++) {
		for(int p : pos[val]) update(p);
		for(int i=0; i+k-1<pos[val].size(); i++) {
			int l=pos[val][i], r=pos[val][i+k-1];
			int temp=get(r, r).mn;
			if(l) temp-=get(l-1, l-1).mx;
			int need=abs(temp)-k;
			if(need<=0) return 1;
			int add=0;
			if(l) {
				if(temp<0) add=get(l-1, l-1).mn-get(0, l-1).mn;
				else add=-get(l-1, l-1).mx+get(0, l-1).mx;
			}
			need-=add;
			if(need<=0) return 1;
			add=0;
			if(r+1<n) {
				if(temp<0) add=get(r+1, n-1).mx-get(r, r).mx;
				else add=-get(r+1, n-1).mn+get(r, r).mn;
			}
			need-=add;
			if(need<=0) return 1;
		}
		for(int p : pos[val]) update(p);
	}
	return 0;
}
int sequence(int N, vector<int> a) {
	n=N;
	pos.resize(n+1);
	tr.resize(4*n);
	lazy.resize(4*n);
	for(int i=0; i<n; i++) pos[a[i]].push_back(i);
	int l=1, r=n, ans=1;
	while(l<=r) {
		int mid=l+r>>1;
		if(can(mid)) ans=mid, l=mid+1;
		else r=mid-1;
	}
	return ans;
}

Compilation message (stderr)

sequence.cpp: In function 'void update(int, int, int, int, int, int)':
sequence.cpp:33:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |  push(pos); int mid=l+r>>1;
      |                     ~^~
sequence.cpp: In function 'node get(int, int, int, int, int)':
sequence.cpp:41:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |  push(pos); int mid=l+r>>1;
      |                     ~^~
sequence.cpp: In function 'node build(int, int, int)':
sequence.cpp:47:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |  int mid=l+r>>1;
      |          ~^~
sequence.cpp: In function 'bool can(int)':
sequence.cpp:54:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |   for(int i=0; i+k-1<pos[val].size(); i++) {
      |                ~~~~~^~~~~~~~~~~~~~~~
sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:87:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   87 |   int mid=l+r>>1;
      |           ~^~

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