Submission #163193

#	Time	Username	Problem	Language	Result	Execution time	Memory
163193		TadijaSebez	역사적 조사 (JOI14_historical)	C++11	100 / 100	358 ms	7024 KiB

historic

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int N=100050;
const int S=317;
ll sum[N],mx;
vector<int> val;
int l[N],r[N],a[N];
vector<int> Qs[N/S+1];
void Add(int x)
{
	sum[x]+=val[x];
	mx=max(mx,sum[x]);
}
void Del(int x){ sum[x]-=val[x];}
ll ans[N];
int main()
{
	int n,q;
	scanf("%i %i",&n,&q);
	for(int i=1;i<=n;i++) scanf("%i",&a[i]),val.pb(a[i]);
	sort(val.begin(),val.end());val.erase(unique(val.begin(),val.end()),val.end());
	for(int i=1;i<=n;i++) a[i]=lower_bound(val.begin(),val.end(),a[i])-val.begin();
	for(int i=1;i<=q;i++) scanf("%i %i",&l[i],&r[i]),Qs[l[i]/S].pb(i);
	for(int i=0;i*S<=n;i++)
	{
		int s=i*S,e=(i+1)*S-1;
		sort(Qs[i].begin(),Qs[i].end(),[&](int i, int j){ return r[i]<r[j];});
		int ptr=e;
		for(int id:Qs[i])
		{
			if(r[id]<=e)
			{
				for(int j=l[id];j<=r[id];j++) Add(a[j]);
				ans[id]=mx;
				for(int j=l[id];j<=r[id];j++) Del(a[j]);
				mx=0;
			}
			else
			{
				while(ptr<r[id]) Add(a[++ptr]);
				ll tmp=mx;
				for(int j=l[id];j<=e;j++) Add(a[j]);
				ans[id]=mx;
				for(int j=l[id];j<=e;j++) Del(a[j]);
				mx=tmp;
			}
		}
		for(int j=e+1;j<=ptr;j++) Del(a[j]);
		mx=0;
	}
	for(int i=1;i<=q;i++) printf("%lld\n",ans[i]);
	return 0;
}

Compilation message (stderr)

historic.cpp: In function 'int main()':
historic.cpp:28:7: warning: unused variable 's' [-Wunused-variable]
   int s=i*S,e=(i+1)*S-1;
       ^
historic.cpp:21:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&q);
  ~~~~~^~~~~~~~~~~~~~~
historic.cpp:22:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%i",&a[i]),val.pb(a[i]);
                        ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
historic.cpp:25:50: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=q;i++) scanf("%i %i",&l[i],&r[i]),Qs[l[i]/S].pb(i);
                        ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 25 / 25
• Subtask 4: 60 / 60