Submission #124334

#	Time	Username	Problem	Language	Result	Execution time	Memory
124334		nvmdava	Fish (IOI08_fish)	C++17	4 / 100	614 ms	18388 KiB

fish

#include <bits/stdc++.h>
using namespace std;
#define N 500005
int pw[N], n, k, m;
vector<vector<int> > f;
int fen[N];

void update(int id){
	while(id < N){
		fen[id]++;
		id += id & -id;
	}
}

int query(int id){
	int res = 0;
	while(id){
		res += fen[id];
		id -= id & -id;
	}
	return res;
}
vector<pair<int, int> > all;
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>k>>m;
	pw[0] = 1;
	f.resize(k);
	for(int i = 1; i <= n; i++) pw[i] = pw[i - 1] * 2 % m;
	for(int i = 1; i <= n; i++){
		int l, t;
		cin>>l>>t; t--;
		f[t].push_back(l);
	}
	for(int i = 0; i < k; i++)
		sort(f[i].begin(), f[i].end());
	
	sort(f.begin(), f.end(), [](const vector<int>& lhs, const vector<int>& rhs){
		return lhs.back() < rhs.back();
	});
	
	long long res = 0;
	
	for(int i = 0; i < k; i++){
		int sz = f[i].size();
		for(int j = 0; j < sz; j++){
			all.push_back({f[i][j], i});
		}
	}
	
	sort(all.begin(), all.end());
	int it = 0;
	for(int i = 0; i < k; i++){
		int sz = f[i].size() - 1;
		while(it != n && all[it].first * 2<= f[i][sz]) update(all[it++].second + 1);
		int ii = 0;
		for(int j = 0; j <= sz; j++){
			ii = upper_bound(f.begin(), f.end(), f[i][j] * 2,[](const int& lhs, const vector<int>& rhs){
				return lhs < rhs.back();
			}) - f.begin();
			res = (res + pw[query(ii) - (ii > i ? j : 0)]) % m;
			if(f[i][j] * 2 > f[i][sz]) break;
		}
	}
	cout<<res;
}

• Subtask 1: 4 / 4
• Subtask 2: 0 / 4
• Subtask 3: 0 / 4
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 5
• Subtask 7: 0 / 6
• Subtask 8: 0 / 6
• Subtask 9: 0 / 6
• Subtask 10: 0 / 6
• Subtask 11: 0 / 7
• Subtask 12: 0 / 7
• Subtask 13: 0 / 7
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5