oj.uz

Submission #217595

# Submission time Handle Problem Language Result Execution time Memory
217595 2020-03-30T10:27:56 Z songc Fish (IOI08_fish) C++14
100 / 100
 776 ms 52344 KB 
#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

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12160 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12160 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12288 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12160 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12288 KB Output is correct
2 Correct 12 ms 12288 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12288 KB Output is correct
2 Correct 220 ms 24824 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12288 KB Output is correct

Subtask #8
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12288 KB Output is correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 17748 KB Output is correct
2 Correct 148 ms 18884 KB Output is correct

Subtask #10
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12340 KB Output is correct
2 Correct 15 ms 12416 KB Output is correct
3 Correct 15 ms 12416 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 20728 KB Output is correct
2 Correct 283 ms 25240 KB Output is correct
3 Correct 280 ms 25840 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 25464 KB Output is correct
2 Correct 285 ms 26232 KB Output is correct

Subtask #13
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 21240 KB Output is correct
2 Correct 291 ms 26096 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 25464 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 27640 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 26744 KB Output is correct
2 Correct 355 ms 32120 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 504 ms 32888 KB Output is correct
2 Correct 361 ms 28024 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 427 ms 31352 KB Output is correct
2 Correct 444 ms 32120 KB Output is correct
3 Correct 475 ms 35304 KB Output is correct
4 Correct 451 ms 31920 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 635 ms 36684 KB Output is correct
2 Correct 776 ms 51192 KB Output is correct
3 Correct 584 ms 52344 KB Output is correct
4 Correct 749 ms 46712 KB Output is correct