oj.uz

Submission #199546

# Submission time Handle Problem Language Result Execution time Memory
199546 2020-02-02T02:24:24 Z arnold518 역사적 조사 (JOI14_historical) C++14
40 / 100
 4000 ms 106128 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 6 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 6 ms 376 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 12 ms 932 KB Output is correct
3 Correct 22 ms 1396 KB Output is correct
4 Correct 42 ms 1468 KB Output is correct
5 Correct 103 ms 2116 KB Output is correct
6 Correct 178 ms 2284 KB Output is correct
7 Correct 169 ms 2472 KB Output is correct
8 Correct 168 ms 2280 KB Output is correct
9 Correct 167 ms 2280 KB Output is correct
10 Correct 118 ms 6804 KB Output is correct
11 Correct 134 ms 6908 KB Output is correct
12 Correct 135 ms 4880 KB Output is correct
13 Correct 122 ms 6856 KB Output is correct
14 Correct 142 ms 6816 KB Output is correct
15 Correct 155 ms 4304 KB Output is correct
16 Correct 172 ms 2280 KB Output is correct
17 Correct 152 ms 1900 KB Output is correct
18 Correct 145 ms 6896 KB Output is correct
19 Correct 141 ms 6804 KB Output is correct
20 Correct 99 ms 7084 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 7 ms 504 KB Output is correct
6 Correct 7 ms 504 KB Output is correct
7 Correct 8 ms 760 KB Output is correct
8 Correct 11 ms 1144 KB Output is correct
9 Correct 19 ms 1644 KB Output is correct
10 Correct 32 ms 1140 KB Output is correct
11 Correct 118 ms 5188 KB Output is correct
12 Correct 72 ms 3648 KB Output is correct
13 Correct 89 ms 5860 KB Output is correct
14 Correct 107 ms 5612 KB Output is correct
15 Correct 119 ms 6884 KB Output is correct
16 Correct 86 ms 7784 KB Output is correct
17 Correct 47 ms 4668 KB Output is correct
18 Correct 73 ms 6704 KB Output is correct
19 Correct 77 ms 8932 KB Output is correct
20 Correct 46 ms 6408 KB Output is correct

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 2492 KB Output is correct
2 Correct 1074 ms 7804 KB Output is correct
3 Correct 1750 ms 50772 KB Output is correct
4 Correct 3212 ms 100376 KB Output is correct
5 Correct 3711 ms 106128 KB Output is correct
6 Execution timed out 4070 ms 52128 KB Time limit exceeded
7 Halted 0 ms 0 KB -