Submission #678165

#	Time	Username	Problem	Language	Result	Execution time	Memory
678165		vjudge1	Fish (IOI08_fish)	C++17	17 / 100	639 ms	45732 KiB

fish

#include <bits/stdc++.h> 

#define X first
#define Y second
#define pb push_back

using namespace std; 

typedef pair<int, int> pii;
typedef long long ll;

const int LOG = 19; 
const int OFF = 1 << LOG;

int n, m, MOD;
int L[OFF], G[OFF], bio[OFF], red[OFF], T[OFF << 1];

vector<int> v, f, gem[OFF];
vector<pii> tr;

inline int add(int a, int b){
	return (a + b) % MOD;
} 

inline int mult(int a, int b){
	return (ll) a * b % MOD; 
}

void update(int x, int val){	
	x += OFF;
	T[x] += val;
	x >>= 1;
	while(x){
		T[x] = mult(T[2 * x], T[2 * x + 1]);
		x >>= 1;
	}
}

int query(int l, int r, int x = 1, int lo = 0, int hi = OFF){
	if(r <= lo || hi <= l) return 1;
	if(l <= lo && hi <= r) return T[x];
	int mi = (lo + hi) >> 1;
	return mult(query(l, r, 2 * x, lo, mi), query(l, r, 2 * x + 1, mi, hi));
}

int init(){
	for(int i = 0; i < 2 * OFF; i++) T[i] = 1; 

	scanf("%d%d%d", &n, &m, &MOD);
	
	for(int i = 0; i < n; i++){
		scanf("%d%d", L + i, G + i);
		G[i]--;
		tr.pb({L[i], i});
		gem[G[i]].pb(L[i]);
	}
	
	//sort
	sort(tr.begin(), tr.end());
	for(pii p : tr) f.pb(p.Y);
	
	for(int i = 0; i < m; i++) sort(gem[i].begin(), gem[i].end());
	
	//red
	for(int i = n - 1; i >= 0; i--){
		int j = G[f[i]];
		if(!bio[j]){
			bio[j] = true;
			red[j] = v.size();
			v.pb(f[i]);
		}
	}
	
	//prebroji
	int ind = f[n - 1];
	int i = 0;
	while(2 * L[f[i]] <= L[ind]){
		update(red[G[f[i]]], 1);
	//	printf("T[%d] ++\n", red[G[f[i]]]);
		i++;
	} 	
	
	//for(int i = OFF; i < 2 * OFF; i++) printf("T[%d] = %d\n", i, T[i]); printf("\n");
	return i - 1; 
}

int main(){	
	int tp = init();
	int sol = 0;
	int ug = 0;
	
	memset(bio, 0, sizeof(bio));
	for(int i = n - 1; i >= 0; i--){
		int ind = f[i];
		int g = G[ind];
		
		if(bio[g] == 1) continue;
		bio[g] = true; 
		
		//printf("G = %d, L = %d\n", g, L[ind]);
		
		if(i == n - 1){
			sol = add(sol, query(0, OFF));
		} else {	
			while(tp >= 0 && 2 * L[f[tp]] > L[ind]){
				update(red[G[f[tp]]], -1);
				tp--;
			}
			while(ug < m){
				int ki = lower_bound(gem[g].begin(), gem[g].end(), L[f[i]] / 2 + 1) - gem[g].begin();
				int kj = lower_bound(gem[g].begin(), gem[g].end(), L[v[ug]] / 2 + 1) - gem[g].begin();
				//printf("siz %d -> %d | %d -> %d\n", L[f[i]] / 2, ki, L[v[ug]] / 2 + 1, kj);
				if(ki == kj) break;
				update(ug, 1 - T[OFF + ug]);
				ug++;
			}
			
			//printf("+ %d ", query(red[g], OFF));
			sol = add(sol, query(red[g], OFF));
			if(ug != red[g]){ 
				sol = add(sol, mult(add(query(ug, red[g]), MOD - 1), query(red[g] + 1, OFF)));
				//printf("+ %d", mult(add(query(ug, red[g]), MOD - 1), query(red[g] + 1, OFF)));
			}
		}
	} 
	printf("%d\n", sol);
	return 0;
}

Compilation message (stderr)

fish.cpp: In function 'int init()':
fish.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |  scanf("%d%d%d", &n, &m, &MOD);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |   scanf("%d%d", L + i, G + i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 4 / 4
• Subtask 3: 0 / 4
• Subtask 4: 4 / 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: 5 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5