oj.uz

Submission #678280

# Submission time Handle Problem Language Result Execution time Memory
678280 2023-01-05T11:34:32 Z vjudge1 Fish (IOI08_fish) C++17
0 / 100
 1 ms 340 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 = 4; 
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)) lo = mi;
				else hi = 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
0 / 4.0

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

Subtask #2
0 / 4.0

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

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #11
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #13
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -