oj.uz

Submission #678165

# Submission time Handle Problem Language Result Execution time Memory
678165 2023-01-05T09:25:19 Z vjudge1 Fish (IOI08_fish) C++17
17 / 100
 639 ms 45732 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));
}

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;
	int ug = 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));
		} else {	
			while(tp >= 0 && 2 * L[f[tp]] > L[ind]){
				update(red[G[f[tp]]], -1);
				tp--;
			}
			while(ug < m){
				int ki = lower_bound(gem[g].begin(), gem[g].end(), L[f[i]] / 2 + 1) - gem[g].begin();
				int kj = lower_bound(gem[g].begin(), gem[g].end(), L[v[ug]] / 2 + 1) - gem[g].begin();
				//printf("siz %d -> %d | %d -> %d\n", L[f[i]] / 2, ki, L[v[ug]] / 2 + 1, kj);
				if(ki == kj) break;
				update(ug, 1 - T[OFF + ug]);
				ug++;
			}
			
			//printf("+ %d ", query(red[g], OFF));
			sol = add(sol, query(red[g], OFF));
			if(ug != red[g]){ 
				sol = add(sol, mult(add(query(ug, red[g]), MOD - 1), query(red[g] + 1, OFF)));
				//printf("+ %d", mult(add(query(ug, 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:49:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |  scanf("%d%d%d", &n, &m, &MOD);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |   scanf("%d%d", L + i, G + i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 10 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
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 18768 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

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

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 18776 KB Output is correct
2 Incorrect 10 ms 18800 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 18772 KB Output is correct
2 Incorrect 218 ms 38928 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 18784 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 18844 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 103 ms 27472 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 18900 KB Output is correct
2 Incorrect 14 ms 19028 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #11
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 132 ms 32652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 39796 KB Output is correct
2 Incorrect 219 ms 40676 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #13
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 33212 KB Output is correct
2 Incorrect 242 ms 40508 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 217 ms 38808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 264 ms 41456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 37836 KB Output is correct
2 Correct 307 ms 43580 KB Output is correct

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 475 ms 42480 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 452 ms 41676 KB Output is correct
2 Incorrect 416 ms 43536 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 639 ms 45732 KB Output isn't correct
2 Halted 0 ms 0 KB -