Submission #217510

#	Time	Username	Problem	Language	Result	Execution time	Memory
217510		songc	Fish (IOI08_fish)	C++14	9 / 100	799 ms	16600 KiB

fish

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
 
int N, K, M;
pii A[505050];
int ans, C[505050], T[2020202];
bool chk[505050], D[505050];

void upd(int id, int s, int e, int t, int v){
	if (e < t || t < s) return;
	if (s == e){
		T[id] = v;
		return;
	}
	int m=s+e>>1;
	upd(id*2, s, m, t, v);
	upd(id*2+1, m+1, e, t, v);
	T[id] = T[id*2] * T[id*2+1] % M;
}

int main(){
	scanf("%d %d %d", &N, &K, &M);
	for (int i=1; i<=N; i++) scanf("%d %d", &A[i].fi, &A[i].se);
	sort(A+1, A+N+1);
	int t=0;
	for (int i=1; i<=4*K; i++) T[i] = 1;
	while (A[t+1].fi*2 <= A[N].fi){
		t++, C[A[t].se]++;
		upd(1, 1, K, A[t].se, C[A[t].se]+1);
	}
	for (int i=N; i>0; i--){
		if (chk[A[i].se]) continue;
		while (t>0 && A[t].fi*2 > A[i].fi){
			if (!chk[A[t].se]) upd(1, 1, K, A[t].se, C[A[t].se]--);
			D[A[t].se] = true;
			t--;
		}
		if (!D[A[i].se]) upd(1, 1, K, A[i].se, C[A[i].se]);
		ans = (ans+T[1])%M;
		chk[A[i].se] = true;
		upd(1, 1, K, A[i].se, 1);
	}
	t=0;
	for (int i=1; i<=4*K; i++) T[i] = 1;
	for (int i=1; i<=K; i++) chk[i]=false, C[i]=0;
	while (A[t+1].fi*2 <= A[N].fi){
		t++, C[A[t].se]++;
		upd(1, 1, K, A[t].se, C[A[t].se]+1);
	}
	for (int i=N; i>0; i--){
		while (t>0 && A[t].fi*2 > A[i].fi){
			upd(1, 1, K, A[t].se, C[A[t].se]--);
			chk[A[t].se] = true;
			t--;
		}
		if (chk[A[i].se]) continue;
		upd(1, 1, K, A[i].se, 1);
		ans = (ans+T[1])%M;
		chk[A[i].se] = true;
		upd(1, 1, K, A[i].se, C[A[i].se]+1);
	}
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

fish.cpp: In function 'void upd(int, int, int, int, int)':
fish.cpp:19:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m=s+e>>1;
        ~^~
fish.cpp: In function 'int main()':
fish.cpp:26:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &N, &K, &M);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:27:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i=1; i<=N; i++) scanf("%d %d", &A[i].fi, &A[i].se);
                           ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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