Submission #199554

#	Time	Username	Problem	Language	Result	Execution time	Memory
199554		arnold518	역사적 조사 (JOI14_historical)	C++14	100 / 100	2344 ms	5616 KiB

historic

#pragma GCC optimize ("O3")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;
const int SQ = 300;

int N, Q, A[MAXN+10], B[MAXN+10], S;
vector<int> comp;

struct Query
{
	int l, r, p;
	bool operator < (const Query &p)
	{
		if(l/SQ==p.l/SQ) return r<p.r;
		return l<p.l;
	}
};

Query query[MAXN+10];

ll tree[MAXN*4+10], ans[MAXN+10];
void update(int pos, ll val)
{
	int node=pos+S-1;
	tree[node]+=val;
	while(node!=1)
	{
		node>>=1;
		tree[node]=max(tree[node*2], tree[node*2+1]);
	}
}
ll qquery() { return tree[1]; }

void push(int x) { update(B[x], A[x]); }
void pop(int x) { update(B[x], -A[x]); }

int main()
{
	int i, j;

	scanf("%d%d", &N, &Q);
	for(i=1; i<=N; i++) scanf("%d", &A[i]), comp.push_back(A[i]);
	sort(comp.begin(), comp.end());
	comp.erase(unique(comp.begin(), comp.end()), comp.end()); S=comp.size();
	while(__builtin_popcount(S)!=1) S++;
	for(i=1; i<=N; i++) B[i]=lower_bound(comp.begin(), comp.end(), A[i])-comp.begin()+1;
	for(i=1; i<=Q; i++) scanf("%d%d", &query[i].l, &query[i].r), query[i].p=i;
	sort(query+1, query+Q+1);

	int l=1, r=1; push(1);
	for(i=1; i<=Q; i++)
	{
		while(r<query[i].r) r++, push(r);
		while(l>query[i].l) l--, push(l);
		while(r>query[i].r) pop(r), r--;
		while(l<query[i].l) pop(l), l++;
		ans[query[i].p]=qquery();
	}
	for(i=1; i<=Q; i++) printf("%lld\n", ans[i]);
}

Compilation message (stderr)

historic.cpp: In function 'int main()':
historic.cpp:48:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
historic.cpp:50:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &Q);
  ~~~~~^~~~~~~~~~~~~~~~
historic.cpp:51:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=N; i++) scanf("%d", &A[i]), comp.push_back(A[i]);
                      ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
historic.cpp:56:61: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=Q; i++) scanf("%d%d", &query[i].l, &query[i].r), query[i].p=i;
                      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~

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