oj.uz

Submission #678283

# Submission time Handle Problem Language Result Execution time Memory
678283 2023-01-05T11:43:20 Z vjudge1 Fish (IOI08_fish) C++17
100 / 100
 991 ms 58356 KB 
#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;
}

Compilation message

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

# Verdict Execution time Memory Grader output
1 Correct 9 ms 18772 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 18772 KB Output is correct

Subtask #3
4.0 / 4.0

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

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 18772 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 18724 KB Output is correct
2 Correct 10 ms 18760 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 18820 KB Output is correct
2 Correct 214 ms 32992 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 18772 KB Output is correct

Subtask #8
6.0 / 6.0

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

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 24928 KB Output is correct
2 Correct 132 ms 29424 KB Output is correct

Subtask #10
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 18900 KB Output is correct
2 Correct 14 ms 18900 KB Output is correct
3 Correct 14 ms 18908 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 28720 KB Output is correct
2 Correct 263 ms 39724 KB Output is correct
3 Correct 237 ms 40256 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 33760 KB Output is correct
2 Correct 215 ms 33660 KB Output is correct

Subtask #13
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 28964 KB Output is correct
2 Correct 229 ms 33456 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 32572 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 34168 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 31500 KB Output is correct
2 Correct 322 ms 35836 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 515 ms 35492 KB Output is correct
2 Correct 426 ms 36784 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 432 ms 36576 KB Output is correct
2 Correct 442 ms 35832 KB Output is correct
3 Correct 549 ms 45472 KB Output is correct
4 Correct 511 ms 43568 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 723 ms 37784 KB Output is correct
2 Correct 920 ms 57324 KB Output is correct
3 Correct 822 ms 58356 KB Output is correct
4 Correct 991 ms 54300 KB Output is correct