제출 #678283

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
678283		vjudge1	Fish (IOI08_fish)	C++17	100 / 100	991 ms	58356 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));
}

bool check(int l1, int l2, int a){
	int k1 = lower_bound(gem[a].begin(), gem[a].end(), l1 / 2 + 1) - gem[a].begin();
	int k2 = lower_bound(gem[a].begin(), gem[a].end(), l2 / 2 + 1) - gem[a].begin();
	return k1 == k2;
}

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;
	
	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));
			//printf("+ %d\n", query(0, OFF));
		} else {	
			while(tp >= 0 && 2 * L[f[tp]] > L[ind]){
				update(red[G[f[tp]]], -1);
				tp--;
			}
			
			int lo = -1, hi = red[g];
			
			while(hi - lo > 1){
				int mi = (lo + hi) >> 1;
				if(check(L[ind], L[v[mi]], g)) hi = mi;
				else lo = mi;
			}	
			
			
			sol = add(sol, query(red[g], OFF));			
			sol = add(sol, mult(add(query(hi, red[g]), MOD - 1), query(red[g] + 1, OFF)));
			//printf("+ %d ", query(red[g], OFF));printf("+ %d\n", mult(add(query(hi, red[g]), MOD - 1), query(red[g] + 1, OFF)));
		}
	} 
	printf("%d\n", sol);
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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