| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 16663 |
2015-09-03T23:16:45 Z |
Qwaz |
역사적 조사 (JOI14_historical) |
C++14 |
|
353 ms |
4212 KB |
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAX = 100020, GROUP_SIZE = 350;
struct query {
int s, e, index;
int getStartGroup() const {
return s/GROUP_SIZE+1;
}
bool operator < (const query &t) const {
int g1 = getStartGroup(), g2 = t.getStartGroup();
if (g1 == g2)
return e < t.e;
return g1 < g2;
}
};
int numEvent, numQuery, qFull, impact[MAX], xList[MAX], xFull;
query queries[MAX];
ll ans[MAX];
int cnt[MAX];
void input() {
scanf("%d%d", &numEvent, &numQuery);
for (int i = 0; i < numEvent; i++) {
scanf("%d", &impact[i]);
xList[xFull++] = impact[i];
}
sort(xList, xList+xFull);
xFull = unique(xList, xList+xFull)-xList;
// renumbering
for (int i = 0; i < numEvent; i++) {
impact[i] = lower_bound(xList, xList+xFull, impact[i]) - xList;
}
for (int i = 0; i < numQuery; i++) {
int f, s;
scanf("%d%d", &f, &s);
// Convert to 0-base
queries[qFull].s = f-1;
queries[qFull].e = s-1;
queries[qFull].index = i;
if (queries[qFull].e < queries[qFull].getStartGroup() * GROUP_SIZE) {
// Calculate immediately
ll tAns = 0;
query &now = queries[qFull];
for (int i = now.s; i <= now.e; i++) {
int tImpact = impact[i];
cnt[tImpact]++;
tAns = max(tAns, (ll)cnt[tImpact] * xList[tImpact]);
}
for (int i = now.s; i <= now.e; i++) {
int tImpact = impact[i];
cnt[tImpact]--;
}
ans[i] = tAns;
} else
// Put into a queue
qFull++;
}
sort(queries, queries+qFull);
}
void solve() {
int currentQuery = 0;
while (currentQuery < qFull) {
// Init count
for (int i = 0; i < xFull; i++)
cnt[i] = 0;
ll maxInRange = 0;
int startGroup = queries[currentQuery].getStartGroup(), startIndex = startGroup * GROUP_SIZE;
for (int lastEvent = startIndex; lastEvent < numEvent; lastEvent++) {
int tImpact = impact[lastEvent];
cnt[tImpact]++;
maxInRange = max(maxInRange, (ll)cnt[tImpact] * xList[tImpact]);
if (startGroup < queries[currentQuery].getStartGroup()) break;
else {
while (startGroup == queries[currentQuery].getStartGroup()
&& currentQuery < qFull && lastEvent == queries[currentQuery].e) {
ll tAns = maxInRange;
query &now = queries[currentQuery];
for (int i = now.s; i < startIndex; i++) {
tImpact = impact[i];
cnt[tImpact]++;
tAns = max(tAns, (ll)cnt[tImpact] * xList[tImpact]);
}
for (int i = now.s; i < startIndex; i++) {
tImpact = impact[i];
cnt[tImpact]--;
}
ans[now.index] = tAns;
currentQuery++;
}
}
}
}
}
void print() {
for (int i = 0; i < numQuery; i++)
printf("%lld\n", ans[i]);
}
int main() {
input();
solve();
print();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
4212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
4212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
4212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
4212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
4212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
4212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
4212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
4212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
4212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
4212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
4212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
4212 KB |
Output is correct |
| 13 |
Correct |
0 ms |
4212 KB |
Output is correct |
| 14 |
Correct |
0 ms |
4212 KB |
Output is correct |
| 15 |
Correct |
0 ms |
4212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
4212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
4212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
4212 KB |
Output is correct |
| 4 |
Correct |
2 ms |
4212 KB |
Output is correct |
| 5 |
Correct |
5 ms |
4212 KB |
Output is correct |
| 6 |
Correct |
7 ms |
4212 KB |
Output is correct |
| 7 |
Correct |
7 ms |
4212 KB |
Output is correct |
| 8 |
Correct |
7 ms |
4212 KB |
Output is correct |
| 9 |
Correct |
7 ms |
4212 KB |
Output is correct |
| 10 |
Correct |
8 ms |
4212 KB |
Output is correct |
| 11 |
Correct |
8 ms |
4212 KB |
Output is correct |
| 12 |
Correct |
8 ms |
4212 KB |
Output is correct |
| 13 |
Correct |
8 ms |
4212 KB |
Output is correct |
| 14 |
Correct |
9 ms |
4212 KB |
Output is correct |
| 15 |
Correct |
10 ms |
4212 KB |
Output is correct |
| 16 |
Correct |
8 ms |
4212 KB |
Output is correct |
| 17 |
Correct |
8 ms |
4212 KB |
Output is correct |
| 18 |
Correct |
8 ms |
4212 KB |
Output is correct |
| 19 |
Correct |
8 ms |
4212 KB |
Output is correct |
| 20 |
Correct |
8 ms |
4212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
4212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
4212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
4212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
4212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
4212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
4212 KB |
Output is correct |
| 7 |
Correct |
3 ms |
4212 KB |
Output is correct |
| 8 |
Correct |
5 ms |
4212 KB |
Output is correct |
| 9 |
Correct |
11 ms |
4212 KB |
Output is correct |
| 10 |
Correct |
12 ms |
4212 KB |
Output is correct |
| 11 |
Correct |
83 ms |
4212 KB |
Output is correct |
| 12 |
Correct |
38 ms |
4212 KB |
Output is correct |
| 13 |
Correct |
66 ms |
4212 KB |
Output is correct |
| 14 |
Correct |
101 ms |
4212 KB |
Output is correct |
| 15 |
Correct |
80 ms |
4212 KB |
Output is correct |
| 16 |
Correct |
197 ms |
4212 KB |
Output is correct |
| 17 |
Correct |
105 ms |
4212 KB |
Output is correct |
| 18 |
Correct |
161 ms |
4212 KB |
Output is correct |
| 19 |
Correct |
160 ms |
4212 KB |
Output is correct |
| 20 |
Correct |
80 ms |
4212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
4212 KB |
Output is correct |
| 2 |
Correct |
34 ms |
4212 KB |
Output is correct |
| 3 |
Correct |
61 ms |
4212 KB |
Output is correct |
| 4 |
Correct |
83 ms |
4212 KB |
Output is correct |
| 5 |
Correct |
113 ms |
4212 KB |
Output is correct |
| 6 |
Correct |
149 ms |
4212 KB |
Output is correct |
| 7 |
Correct |
175 ms |
4212 KB |
Output is correct |
| 8 |
Correct |
188 ms |
4212 KB |
Output is correct |
| 9 |
Correct |
214 ms |
4212 KB |
Output is correct |
| 10 |
Correct |
264 ms |
4212 KB |
Output is correct |
| 11 |
Correct |
260 ms |
4212 KB |
Output is correct |
| 12 |
Correct |
256 ms |
4212 KB |
Output is correct |
| 13 |
Correct |
284 ms |
4212 KB |
Output is correct |
| 14 |
Correct |
313 ms |
4212 KB |
Output is correct |
| 15 |
Correct |
353 ms |
4212 KB |
Output is correct |
| 16 |
Correct |
347 ms |
4212 KB |
Output is correct |
| 17 |
Correct |
344 ms |
4212 KB |
Output is correct |
| 18 |
Correct |
334 ms |
4212 KB |
Output is correct |
| 19 |
Correct |
320 ms |
4212 KB |
Output is correct |
| 20 |
Correct |
306 ms |
4212 KB |
Output is correct |
| 21 |
Correct |
307 ms |
4212 KB |
Output is correct |
| 22 |
Correct |
303 ms |
4212 KB |
Output is correct |
| 23 |
Correct |
305 ms |
4212 KB |
Output is correct |
| 24 |
Correct |
293 ms |
4212 KB |
Output is correct |
| 25 |
Correct |
271 ms |
4212 KB |
Output is correct |
