Submission #907172

#	Time	Username	Problem	Language	Result	Execution time	Memory
907172		bug_limit_exceeded	역사적 조사 (JOI14_historical)	C++17	40 / 100	4089 ms	13220 KiB

historic

//-----------------this template is from cp-algorithms.com--------------
#pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define fi first
#define se second

typedef long long ll;

const int N = 1e5 + 5;

int block_size;
int arr[N];

vector<int> cnt(N), id(N);
set<pair<ll, int>> ans;

void add(int idx){
	int x = arr[idx];
	if(cnt[x]){
		ans.erase({(ll)id[x] * cnt[x], x});
	}
	cnt[x]++;
	ans.insert({(ll)id[x] * cnt[x], x});
}
void remove(int idx){
	int x = arr[idx];
	ans.erase({(ll)id[x] * cnt[x], x});
	cnt[x]--;
	if(cnt[x]){
		ans.insert({(ll)id[x] * cnt[x], x});
	}
}
struct Query {
    int l, r, idx;
    bool operator<(Query other) const {
        return make_pair(l / block_size, r) < make_pair(other.l / block_size, other.r);
    }
};
vector<ll> mo_s_algorithm(vector<Query> queries) {
    vector<ll> answers(queries.size(), -1);
    sort(queries.begin(), queries.end());

    // TODO: initialize data structure

    int cur_l = 0;
    int cur_r = -1;
    // invariant: data structure will always reflect the range [cur_l, cur_r]
    for(Query q : queries){
        while (cur_l > q.l) add(--cur_l);
        while (cur_r < q.r) add(++cur_r);
        while (cur_l < q.l) remove(cur_l++);
        while (cur_r > q.r) remove(cur_r--);
        answers[q.idx] = (*ans.rbegin()).fi;
    }
    return answers;
}
void Solve(){
	int n, q;
	cin>>n>>q;
	vector<int> tmp(n);
	map<int, int> myMap;
	int cur = 1;
	for(int i = 0; i < n; i++){
		cin>>tmp[i];
		if(!myMap.count(tmp[i])){
			myMap[tmp[i]] = cur++;
		}
	}
	for(int i = 0; i < n; i++){
		arr[i] = myMap[tmp[i]];
		id[arr[i]] = tmp[i];
	}
	block_size = sqrt(n) + 1;

	vector<Query> v(q);
	for(int i = 0; i < q; i++){
		cin>>v[i].l>>v[i].r;
		v[i].l--; v[i].r--;
		v[i].idx = i;
	}
	vector<ll> res = mo_s_algorithm(v);
	for(auto x: res){
		cout<<x<<nl;
	}

}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	Solve();
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 25 / 25
• Subtask 4: 0 / 60