Submission #199546

#	Time	Username	Problem	Language	Result	Execution time	Memory
199546		arnold518	역사적 조사 (JOI14_historical)	C++14	40 / 100	4070 ms	106128 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 = 330;

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/SQ<p.l/SQ;
	}
};

Query query[MAXN+10];

int cnt[MAXN+10];
ll ans[MAXN+10];
priority_queue<ll> PQ1, PQ2;
void push(int x) { PQ2.push((ll)A[x]*cnt[B[x]]); cnt[B[x]]++; PQ1.push((ll)A[x]*cnt[B[x]]); }
void pop(int x) { PQ2.push((ll)A[x]*cnt[B[x]]); cnt[B[x]]--; PQ1.push((ll)A[x]*cnt[B[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();
	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);
	
	for(i=1; i<=S; i++) PQ1.push(0);
	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++;
		while(!PQ1.empty() && !PQ2.empty() && PQ1.top()==PQ2.top()) PQ1.pop(), PQ2.pop();
		ans[query[i].p]=PQ1.top();
	}
	for(i=1; i<=Q; i++) printf("%lld\n", ans[i]);
}

Compilation message (stderr)

historic.cpp: In function 'int main()':
historic.cpp:38:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
historic.cpp:40: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:41: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:45: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: 0 / 60