oj.uz

Submission #259585

# Submission time Handle Problem Language Result Execution time Memory
259585 2020-08-08T03:23:01 Z 임성재(#5054) 역사적 조사 (JOI14_historical) C++17
5 / 100
 4000 ms 7396 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 ll sz = 1;

ll n, q;
ll x[100010];
ll cnt[100010];
ll ans[100010];
vector<ll> v;
vector<pair<pll, ll>> qr;
multiset<ll> S;

void add(int k) {
	if(cnt[k] > 0) S.erase(cnt[k] * v[k]);
	cnt[k]++;
	if(cnt[k] > 0) S.insert(cnt[k] * v[k]);
}

void erase(int k) {
	if(cnt[k] > 0) S.erase(cnt[k] * v[k]);
	cnt[k]--;
	if(cnt[k] > 0) S.insert(cnt[k] * v[k]);
}

ll cal() {
	ll ret = 0;
	for(auto it : S) {
		ret = max(it, ret);
	}

	return ret;
}

int main() {
	fast;

	cin >> n >> q;

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

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

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

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

		qr.eb(mp(a, b), i);
	}

	sort(all(qr), [](pair<pll, ll> i, pair<pll, ll> j) {
		if(i.fi.fi / sz == j.fi.fi / sz) return i.fi.se < j.fi.se;
		return i.fi.fi < j.fi.fi;
	});

	int s = qr[0].fi.fi;
	int e = qr[0].fi.se;

	for(int i=s; i<=e; i++) {
		add(x[i]);
	}

	ans[qr[0].se] = cal();

	for(int i=1; i<q; i++) {
		while(s < qr[i].fi.fi) erase(x[s++]);
		while(s > qr[i].fi.fi) add(x[--s]);
		while(e < qr[i].fi.se) add(x[++e]);
		while(e > qr[i].fi.se) erase(x[e--]);

		ans[qr[i].se] = cal();
	}

	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 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 7 ms 384 KB Output is correct
18 Correct 26 ms 384 KB Output is correct
19 Correct 102 ms 512 KB Output is correct
20 Correct 444 ms 760 KB Output is correct
21 Correct 1006 ms 852 KB Output is correct
22 Incorrect 1154 ms 872 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 4 ms 512 KB Output is correct
8 Correct 9 ms 764 KB Output is correct
9 Correct 18 ms 896 KB Output is correct
10 Correct 16 ms 1280 KB Output is correct
11 Correct 86 ms 5852 KB Output is correct
12 Correct 69 ms 2044 KB Output is correct
13 Correct 164 ms 3664 KB Output is correct
14 Correct 161 ms 5100 KB Output is correct
15 Correct 96 ms 7396 KB Output is correct
16 Execution timed out 4043 ms 6668 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 7 ms 384 KB Output is correct
18 Correct 26 ms 384 KB Output is correct
19 Correct 102 ms 512 KB Output is correct
20 Correct 444 ms 760 KB Output is correct
21 Correct 1006 ms 852 KB Output is correct
22 Incorrect 1154 ms 872 KB Output isn't correct
23 Halted 0 ms 0 KB -