제출 #1286955

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1286955		kerem	역사적 조사 (JOI14_historical)	C++20	40 / 100	4089 ms	13696 KiB

historic

#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define pb push_back
#define emb emplace_back
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define sp << " " <<
#define N 300000
#define inf (int)1e9
typedef pair<int,int> ii;
typedef tuple<int,int,int> iii;

const int kok=320;
struct Item{
	int l,r,i;
	Item(int ll,int rr,int ii){
		l=ll;r=rr;i=ii;
	}
	bool operator <(Item other){
		return make_pair(l/kok,r)<make_pair(other.l/kok,other.r);
	}
};
void solve(){
	int n,q;
	cin >> n >> q;
	int a[n+1];
	vector<Item> query;
	for(int i=1;i<=n;i++)
		cin >> a[i];
	for(int i=0;i<q;i++){
		int l,r;
		cin >> l >> r;
		query.emb(l,r,i);
	}
	sort(all(query));
	map<int,int> mp,s;
	int l=1,r=1,ans[q];
	
	auto del=[&s](int x){
		if(s.find(x)!=s.end()){
			if(s[x]==1) s.erase(x);
			else s[x]--;
		}
	};
	auto add=[&s](int x){
		if(x>0) s[x]++;
	};
	
	for(auto [ql,qr,i]:query){
		while(r<qr+1){
			del(a[r]*mp[a[r]]);
			++mp[a[r]];
			add(a[r]*mp[a[r]]);
			++r;
		}
		while(r>qr+1){
			--r;
			del(a[r]*mp[a[r]]);
			--mp[a[r]];
			add(a[r]*mp[a[r]]);
		}
		while(l<ql){
			del(a[l]*mp[a[l]]);
			--mp[a[l]];
			add(a[l]*mp[a[l]]);
			++l;
		}
		while(l>ql){
			--l;
			del(a[l]*mp[a[l]]);
			++mp[a[l]];
			add(a[l]*mp[a[l]]);
		}
		//~ cout << ql sp qr sp i << "\n";
		//~ cout << ":" sp l sp r << "\n";
		//~ for(auto i:mp)
			//~ cout << i.fr sp i.sc << "\n";
		//~ cout << "------\n";
		//~ for(auto i:s)
			//~ cout << i.fr sp i.sc << "\n";
		//~ cout << "\n";
		ans[i]=s.rbegin()->fr;
	}
	for(int i=0;i<q;i++)
		cout << ans[i] << "\n";
}
int32_t main(){
	//~ freopen("hopscotch.in","r",stdin);
	//~ freopen("hopscotch.out","w",stdout);
	
	cout << fixed << setprecision(0);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	
	int test=1;
	//~ cin >> test;
	while(test--) solve();
}

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