Submission #784530

#	Time	Username	Problem	Language	Result	Execution time	Memory
784530		Lyrically	Stone Arranging 2 (JOI23_ho_t1)	C++17	60 / 100	2073 ms	39144 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
int read(){int x;scanf("%lld",&x);return x;}
void print(int x){printf("%lld\n",x);}
void file(string s)
{
	freopen((s+".in").c_str(),"r",stdin);
	freopen((s+".out").c_str(),"w",stdout);
}
const int mod=998244353;
int n;
int a[200005];
int nxt[200005];
int seg[200005*4],tag[200005*4];
void upd(int id){seg[id]=seg[id*2]+seg[id*2+1];}
void pushdown(int id,int l,int r)
{
	int mid=(l+r)/2;
	if(tag[id])
	{
		seg[id*2]=(mid-l+1)*tag[id];
		seg[id*2+1]=(r-mid)*tag[id];
		tag[id*2]=tag[id*2+1]=tag[id];
		tag[id]=0;
	}
}
void assign(int id,int l,int r,int ql,int qr,int x)
{
	if(l==ql&&r==qr)
	{
		seg[id]=x*(r-l+1);
		tag[id]=x;return;
	}
	int mid=(l+r)/2;
	if(qr<=mid){assign(id*2,l,mid,ql,qr,x);}
	else if(ql>mid){assign(id*2+1,mid+1,r,ql,qr,x);}
	else{assign(id*2,l,mid,ql,mid,x);assign(id*2+1,mid+1,r,mid+1,qr,x);}
	upd(id);
}
int query(int id,int l,int r,int x)
{
	if(l==r){return seg[id];}
	pushdown(id,l,r);
	int mid=(l+r)/2;
	if(x<=mid){return query(id*2,l,mid,x);}
	return query(id*2+1,mid+1,r,x);
}
set<int> v[200005];
signed main()
{
	n=read();
	map<int,int> vis;
	vector<int> lsh;
	rep1(i,n){a[i]=read();lsh.pb(a[i]);}
	sort(lsh.begin(),lsh.end());
	rep1(i,n)
	{
		int x=a[i];
		a[i]=lower_bound(lsh.begin(),lsh.end(),a[i])-lsh.begin()+1;
		vis[a[i]]=x;
	}
	rep1(i,n)
	{
		if(!v[a[i]].empty())
		{
			//cout<<nxt[a[i]]<<" "<<i<<" "<<a[i]<<endl;
			int x=*(--v[a[i]].end());
			assign(1,1,n,x,i,a[i]);
			for(int j=x;j<=i;j++)
			{
				v[a[j]].erase(j);
			}
			v[a[i]].insert(i);
		}
		else
		{
			//cout<<i<<" "<<i<<" "<<a[i]<<endl;
			assign(1,1,n,i,i,a[i]);
			v[a[i]].insert(i);
		}
	}
	rep1(i,n)
	{
		printf("%lld\n",vis[query(1,1,n,i)]);
	}
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'long long int read()':
Main.cpp:8:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 | int read(){int x;scanf("%lld",&x);return x;}
      |                  ~~~~~^~~~~~~~~~~
Main.cpp: In function 'void file(std::string)':
Main.cpp:12:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |  freopen((s+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:13:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |  freopen((s+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 25 / 25
• Subtask 2: 35 / 35
• Subtask 3: 0 / 40