Submission #217595

#	Time	Username	Problem	Language	Result	Execution time	Memory
217595		songc	Fish (IOI08_fish)	C++14	100 / 100	776 ms	52344 KiB

fish

#include <bits/stdc++.h>
#define pb push_back
#define lb lower_bound
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
 
int N, K, M, num;
pii A[505050];
int P[505050], X[505050];
int ans, T[2020202];
vector<int> F[505050];
bool chk[505050];

void upd(int id, int s, int e, int t, int v){
	if (e < t || t < s) return;
	if (s == e){
		T[id] = (T[id] + v) % M;
		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 query(int id, int s, int e, int ts, int te){
	if (e < ts || te < s) return 1;
	if (ts <= s && e <= te) return T[id];
	int m=s+e>>1;
	return query(id*2, s, m, ts, te)*query(id*2+1, m+1, e, ts, te)%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);
	num=K;
	for (int i=N; i>0; i--){
		if (!P[A[i].se]){
			X[num]=A[i].fi, F[num].pb(A[N].fi);
			P[A[i].se]=num--, chk[i]=true;
		}
		A[i].se = P[A[i].se], F[A[i].se].pb(A[i].fi);
	}
	int t=0;
	for (int i=1; i<=4*K; i++) T[i] = 1;
	for (int i=1; i<=N; i++){
		if (!chk[i]) continue;
		while (t<N && 2*A[t+1].fi <= A[i].fi){
			upd(1, 1, K, A[++t].se, 1);
			F[A[t].se].pop_back();
		}
		ans = (ans + query(1, 1, K, 1, A[i].se)) % M;
		int x = lb(X+1, X+K+1, 2*F[A[i].se].back())-X-1;
		ans = (ans + M + query(1, 1, K, 1, A[i].se-1)*(query(1, 1, K, A[i].se+1, x)-1)) % M;
	}
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

fish.cpp: In function 'void upd(int, int, int, int, int)':
fish.cpp:23:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m=s+e>>1;
        ~^~
fish.cpp: In function 'int query(int, int, int, int, int)':
fish.cpp:32:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m=s+e>>1;
        ~^~
fish.cpp: In function 'int main()':
fish.cpp:37: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:38: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: 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