Submission #31959

#	Time	Username	Problem	Language	Result	Execution time	Memory
31959		huynd2001	역사적 조사 (JOI14_historical)	C++14	40 / 100	4000 ms	16156 KiB

historic

/*huypheu
5 5
9 8 7 8 9
1 2
3 4
4 4
1 4
2 4
*/

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

int le[100007],ri[100007];
int ans[100007];
map <int,int> mymap;
int it[400007];
int blo;
int a[100007],b[100007];
int v[100007];

vector <int> ve;

void update(int node,int l,int r,int x,int p)
{
	// if(node==1) cout << x << " " << p << endl;
	// cout << node << " " << l << " " << r << endl;
	if(l>r || x<l || r<x) return ;
	if(l==r)
	{
		it[node]+=p;
		// cout << node << " " << p << endl;
		return ;
	}
	int mid=(l+r)/2;
	update(node*2,l,mid,x,p);
	update(node*2+1,mid+1,r,x,p);
	it[node]=max(it[node*2],it[node*2+1]);
	return ;
}

int get(int node,int l,int r,int x,int y)
{
	if(l>r || y<l || r<x) return 0;
	if(x<=l && r<=y)
	{
		return it[node];
	}
	int mid=(l+r)/2;
	return max(get(node*2,l,mid,x,y),get(node*2+1,mid+1,r,x,y));
}

bool dcp1(int x,int y)
{
	return (a[x]<a[y]);
}

bool dcp(int x,int y)
{
	if((le[x]/blo)!=(le[y]/blo)) return ((le[x]/blo)<(le[y]/blo));
	else if(ri[x]!=ri[y]) return (ri[x]<ri[y]); else return (le[x]<le[y]);
}

signed main()
{
	// ios_base::sync_with_stdio(false);
	// cin.tie(0);
	int n,q;
	scanf("%lld %lld",&n,&q);
	// cin >> n >> q;
	blo=(int)sqrt(n);
	// cout << blo << endl;
	int m=0;
	set <int> se;
	for(int i=1;i<=n;i++)
	{
		// cin >> a[i];
		scanf("%lld",&a[i]);
		// cout << a[i] << " ";
		se.insert(a[i]);
		v[i]=i;
		// m=max(m,b[i]);
	}
	sort(v+1,v+n+1,dcp1);
	for(int i=1;i<=n;i++)
	{
		if(i==1 || a[v[i]]!=a[v[i-1]]) m++;
		b[v[i]]=m;
	}
	// for(int i=1;i<=n;i++) cout << b[i] << " " << a[i] << endl;
	// 	cout << endl;
	// for(int i=1;i<=n;i++) cout << b[i] << " ";
	// 	cout << endl;
	// cout << endl;
	for(int i=1;i<=q;i++)
	{
		scanf("%lld %lld",&le[i],&ri[i]);
		ve.push_back(i);
	}
	sort(ve.begin(),ve.end(),dcp);
	int l=le[ve[0]],r=le[ve[0]]-1;
	for(int i=0;i<ve.size();i++)
	{
		// cout << le[ve[i]] << " " << ri[ve[i]] << endl;
		while(l>le[ve[i]])
		{
			l--;
			update(1,1,m,b[l],a[l]);
		}
		while(l<le[ve[i]])
		{
			l++;
			update(1,1,m,b[l-1],-a[l-1]);
		}
		while(r<ri[ve[i]])
		{
			r++;
			update(1,1,m,b[r],a[r]);
		}
		while(r>ri[ve[i]])
		{
			r--;
			update(1,1,m,b[r+1],-a[r+1]);
		}
		ans[ve[i]]=get(1,1,m,1,m);
		// cout << it[1] << endl;
	}
	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:103:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<ve.size();i++)
               ^
historic.cpp:70:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld",&n,&q);
                          ^
historic.cpp:79:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&a[i]);
                      ^
historic.cpp:98:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld",&le[i],&ri[i]);
                                   ^

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