oj.uz

Submission #259568

# Submission time Handle Problem Language Result Execution time Memory
259568 2020-08-08T02:42:37 Z 임성재(#5054) 역사적 조사 (JOI14_historical) C++17
5 / 100
 4000 ms 11376 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;

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

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--;

		if(a > b) swap(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++) {
		
		S.clear();
		for(int j=0; j<=n; j++) S.insert(0), cnt[j] = 0;

		ll s = i * sz;
		ll e = i * sz;
		
		for(auto j : qr[i]) {
			for( ; e <= j.fi.fi; e++) {
				S.erase(- v[x[e]] * cnt[x[e]]);
				cnt[x[e]]++;
				S.insert(- v[x[e]] * cnt[x[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 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 4 ms 536 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 5 ms 512 KB Output is correct
15 Correct 4 ms 384 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 4 ms 536 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 5 ms 512 KB Output is correct
15 Correct 4 ms 384 KB Output is correct
16 Correct 10 ms 384 KB Output is correct
17 Correct 29 ms 384 KB Output is correct
18 Correct 70 ms 512 KB Output is correct
19 Correct 146 ms 632 KB Output is correct
20 Correct 319 ms 888 KB Output is correct
21 Correct 488 ms 1144 KB Output is correct
22 Incorrect 527 ms 1144 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 7 ms 384 KB Output is correct
3 Correct 16 ms 384 KB Output is correct
4 Correct 30 ms 384 KB Output is correct
5 Correct 113 ms 580 KB Output is correct
6 Correct 115 ms 640 KB Output is correct
7 Correct 244 ms 928 KB Output is correct
8 Correct 560 ms 1444 KB Output is correct
9 Correct 1259 ms 2432 KB Output is correct
10 Correct 2683 ms 4468 KB Output is correct
11 Execution timed out 4054 ms 11376 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 4 ms 536 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 5 ms 512 KB Output is correct
15 Correct 4 ms 384 KB Output is correct
16 Correct 10 ms 384 KB Output is correct
17 Correct 29 ms 384 KB Output is correct
18 Correct 70 ms 512 KB Output is correct
19 Correct 146 ms 632 KB Output is correct
20 Correct 319 ms 888 KB Output is correct
21 Correct 488 ms 1144 KB Output is correct
22 Incorrect 527 ms 1144 KB Output isn't correct
23 Halted 0 ms 0 KB -