oj.uz

Submission #259550

# Submission time Handle Problem Language Result Execution time Memory
259550 2020-08-08T02:21:29 Z 임성재(#5054) 역사적 조사 (JOI14_historical) C++17
5 / 100
 4000 ms 10988 KB 
#include<bits/stdc++.h>  
using namespace std;  
  
#define fast ios::sync_with_stdio(false);cin.tie(NULL)  
#define fi first  
#define se second  
#define all(v) (v).begin(),(v).end()  
#define pb push_back  
#define eb emplace_back
#define pre(a) cout<<fixed; cout.precision(a)
#define mp make_pair
  
typedef long long ll;  
typedef pair<int,int> pii;  
typedef pair<ll,ll> pll;  
const ll INF = 1e18;
const int inf = 1e9;
const int sz = 333;

int n, q;
int x[100010];
ll ans[100010];
ll cnt[100010];
vector<pair<pii, int>> qr[sz];
vector<ll> v;

int main() {
	fast;

	cin >> n >> q;

	v.eb(0);

	for(int i=1; i<=n; i++) {
		cin >> x[i];
		v.eb(x[i]);
	}

	sort(all(v));
	v.erase(unique(all(v)), v.end());

	for(int i=1; i<=n; i++) {
		x[i] = lower_bound(all(v), x[i]) - v.begin();
	}

	for(int i=1; i<=q; i++) {
		int a, b;
		cin >> a >> b;

		qr[a / sz].eb(mp(b, a), i);
	}

	for(int i=0; i<sz; i++) {
		sort(all(qr[i]));
	}

	for(int i=0; i<sz; i++) {
		memset(cnt, 0, sizeof(cnt));

		multiset<ll> S;
		for(int i=0; i<=n; i++) S.insert(0);

		int s = i * sz, e = i * sz;
		
		for(auto j : qr[i]) {
			while(e <= j.fi.fi) {
				S.erase(- v[x[e]] * cnt[x[e]]);
				cnt[x[e]]++;
				S.insert(- v[x[e]] * cnt[x[e]]);
				
				e++;
			}

			for(int k = s; k < j.fi.se; k++) {
				S.erase(- v[x[k]] * cnt[x[k]]);
				cnt[x[k]]--;
				S.insert(- v[x[k]] * cnt[x[k]]);
			}

			ans[j.se] = -*S.begin();

			for(int k = s; k < j.fi.se; k++) {
				S.erase(- v[x[k]] * cnt[x[k]]);
				cnt[x[k]]++;
				S.insert(- v[x[k]] * cnt[x[k]]);
			}
		}
	}

	for(int i=1; i<=q; i++) {
		cout << ans[i] << "\n";
	}
}

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1152 KB Output is correct
2 Correct 11 ms 1152 KB Output is correct
3 Correct 14 ms 1152 KB Output is correct
4 Correct 14 ms 1152 KB Output is correct
5 Correct 14 ms 1204 KB Output is correct
6 Correct 13 ms 1152 KB Output is correct
7 Correct 14 ms 1152 KB Output is correct
8 Correct 14 ms 1200 KB Output is correct
9 Correct 14 ms 1152 KB Output is correct
10 Correct 14 ms 1280 KB Output is correct
11 Correct 14 ms 1152 KB Output is correct
12 Correct 14 ms 1152 KB Output is correct
13 Correct 14 ms 1152 KB Output is correct
14 Correct 14 ms 1152 KB Output is correct
15 Correct 14 ms 1196 KB Output is correct
16 Correct 21 ms 1152 KB Output is correct
17 Correct 41 ms 1152 KB Output is correct
18 Correct 80 ms 1268 KB Output is correct
19 Correct 150 ms 1400 KB Output is correct
20 Correct 317 ms 1528 KB Output is correct
21 Correct 491 ms 1684 KB Output is correct
22 Incorrect 528 ms 1664 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1280 KB Output is correct
2 Correct 17 ms 1152 KB Output is correct
3 Correct 23 ms 1152 KB Output is correct
4 Correct 39 ms 1280 KB Output is correct
5 Correct 118 ms 1280 KB Output is correct
6 Correct 122 ms 1408 KB Output is correct
7 Correct 262 ms 1656 KB Output is correct
8 Correct 549 ms 2168 KB Output is correct
9 Correct 1212 ms 2944 KB Output is correct
10 Correct 2609 ms 4596 KB Output is correct
11 Execution timed out 4056 ms 10988 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1152 KB Output is correct
2 Correct 11 ms 1152 KB Output is correct
3 Correct 14 ms 1152 KB Output is correct
4 Correct 14 ms 1152 KB Output is correct
5 Correct 14 ms 1204 KB Output is correct
6 Correct 13 ms 1152 KB Output is correct
7 Correct 14 ms 1152 KB Output is correct
8 Correct 14 ms 1200 KB Output is correct
9 Correct 14 ms 1152 KB Output is correct
10 Correct 14 ms 1280 KB Output is correct
11 Correct 14 ms 1152 KB Output is correct
12 Correct 14 ms 1152 KB Output is correct
13 Correct 14 ms 1152 KB Output is correct
14 Correct 14 ms 1152 KB Output is correct
15 Correct 14 ms 1196 KB Output is correct
16 Correct 21 ms 1152 KB Output is correct
17 Correct 41 ms 1152 KB Output is correct
18 Correct 80 ms 1268 KB Output is correct
19 Correct 150 ms 1400 KB Output is correct
20 Correct 317 ms 1528 KB Output is correct
21 Correct 491 ms 1684 KB Output is correct
22 Incorrect 528 ms 1664 KB Output isn't correct
23 Halted 0 ms 0 KB -