oj.uz

Submission #124334

# Submission time Handle Problem Language Result Execution time Memory
124334 2019-07-03T06:06:28 Z nvmdava Fish (IOI08_fish) C++17
4 / 100
 614 ms 18388 KB 
#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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 476 KB Output isn't correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 504 KB Output isn't correct

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 504 KB Output isn't correct

Subtask #9
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 86 ms 4752 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 508 KB Output is correct
2 Incorrect 5 ms 632 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #11
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 143 ms 7912 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 231 ms 9860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 120 ms 8184 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 250 ms 9716 KB Output isn't correct

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 269 ms 10484 KB Output isn't correct

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 225 ms 10216 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 441 ms 15272 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 303 ms 16444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 614 ms 18388 KB Output isn't correct
2 Halted 0 ms 0 KB -