Submission #701621

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
701621	2023-02-21T15:29:48 Z	lovrot	Event Hopping (BOI22_events)	C++17	Compilation error	0 ms	0 KB

events

#include <cstdio>
#include <vector> 
#include <queue>
#include <stack> 
#include <algorithm> a#include <cstdio>
#include <vector> 
#include <queue>
#include <stack> 
#include <algorithm> 
#include <cstring>
#include <map>

#define X first
#define Y second
#define pb push_back 

using namespace std; 

typedef pair<int, int> pii; 

const int LOG = 18; 
const int OFF = 1 << LOG; 

int n, t; 
int S[OFF], E[OFF], up[OFF][LOG], T[2 * OFF]; 

vector<int> vri, sweep;  
map<int, int> mp; 

int merge(int a, int b) { 
	if(a == -1 || b == -1) return a > -1 ? a : b; 
	return S[a] < S[b] ? a : b; 
}

void update(int a, int val) {
	a += OFF; 
	T[a] = merge(T[a], val); 
	a /= 2;
	while(a) {
		T[a] = merge(T[2 * a], T[2 * a + 1]); 
		a /= 2; 
	}
}

int query(int l, int r, int lo = 0, int hi = OFF, int x = 1) {
	if(r <= lo || hi <= l) return -1;
	if(l <= lo && hi <= r) return T[x];
	int mi = (lo + hi) / 2;
	return merge(query(l, r, lo, mi, 2 * x), query(l, r, mi, hi, 2 * x + 1)); 
}

bool comp(int a, int b) {
	return E[a] == E[b] ? S[a] < S[b] : E[a] < E[b];
}

pii climb(int a, int b) {
	int res = 0; 
	for(int i = LOG - 1; i >= 0; i--) {
		if(up[b][i] == -1) continue; 
		else if(E[a] < S[up[b][i]]) { 
			b = up[b][i]; 
			res += 1 << i; 
		}
	}
	if(E[a] < S[b] && up[b][0] != -1) {
		b = up[b][0]; 
		res++;
	}
	return {b, res}; 
}

int main() {
	memset(up, -1, sizeof(up)); 
	memset(T, -1, sizeof(T));

	scanf("%d%d", &n, &t); 
	for(int i = 0; i < n; i++) {
		scanf("%d%d", S + i, E + i); 
		vri.pb(S[i]);
		vri.pb(E[i]); 
		//vri.pb(E[i] + 1); 
	}
	
	sort(vri.begin(), vri.end());
	vri.erase(unique(vri.begin(), vri.end()), vri.end());  
	
	for(int i = 0; i < (int) vri.size(); i++) mp[vri[i]] = i; 
	
	for(int i = 0; i < n; i++) {
		S[i] = mp[S[i]]; 
		E[i] = mp[E[i]]; 
		//printf("Si = %d Ei = %d\n", S[i] + 1, E[i] + 1);
		sweep.pb(i); 
	}

	sort(sweep.begin(), sweep.end(), comp); 

	for(int i : sweep) {
		up[i][0] = query(S[i], E[i] + 1); 
		update(E[i], i); 
		if(S[i] <= S[up[i][0]]) up[i][0] = -1;
		//printf("UP%d = %d\n", i, up[i][0]);
	}

	for(int j = 1; j < LOG; j++)
		for(int i = 0; i < n; i++)
			if(up[i][j - 1] != -1) up[i][j] = up[up[i][j - 1]][j - 1]; 

	for(int i = 0; i < t; i++) {
		int s, e; 
		scanf("%d%d", &s, &e); 
		//printf("%d %d\n", s, e);
		s--; 
		e--; 
		// if(t >= 20) continue;
		if(e == s) {
			printf("0\n");
		} else if(E[e] < E[s]) {
			printf("impossible\n");  
		} else {
			pii r = climb(s, e); 
			if(S[r.X] <= E[s] && E[s] <= E[r.X]) printf("%d\n", r.Y + 1); 
			else printf("impossible\n");
		}
	}
	return 0; 
}
#include <cstring>
#include <map>

#define X first
#define Y second
#define pb push_back 

using namespace std; 

typedef pair<int, int> pii; 

const int LOG = 18; 
const int OFF = 1 << LOG; 

int n, t; 
int S[OFF], E[OFF], up[OFF][LOG], T[2 * OFF]; 

vector<int> vri, sweep;  
map<int, int> mp; 

int merge(int a, int b) { 
	if(a == -1 || b == -1) return a > -1 ? a : b; 
	return S[a] < S[b] ? a : b; 
}

void update(int a, int val) {
	a += OFF; 
	T[a] = merge(T[a], val); 
	a /= 2;
	while(a) {
		T[a] = merge(T[2 * a], T[2 * a + 1]); 
		a /= 2; 
	}
}

int query(int l, int r, int lo = 0, int hi = OFF, int x = 1) {
	if(r <= lo || hi <= l) return -1;
	if(l <= lo && hi <= r) return T[x];
	int mi = (lo + hi) / 2;
	return merge(query(l, r, lo, mi, 2 * x), query(l, r, mi, hi, 2 * x + 1)); 
}

bool comp(int a, int b) {
	return E[a] == E[b] ? S[a] < S[b] : E[a] < E[b];
}

pii climb(int a, int b) {
	int res = 0; 
	for(int i = LOG - 1; i >= 0; i--) {
		if(up[b][i] == -1) continue; 
		else if(E[a] < S[up[b][i]]) { 
			b = up[b][i]; 
			res += 1 << i; 
		}
	}
	if(E[a] < S[b] && up[b][0] != -1) {
		b = up[b][0]; 
		res++;
	}
	return {b, res}; 
}

int main() {
	memset(up, -1, sizeof(up)); 
	memset(T, -1, sizeof(T));

	scanf("%d%d", &n, &t); 
	for(int i = 0; i < n; i++) {
		scanf("%d%d", S + i, E + i); 
		vri.pb(S[i]);
		vri.pb(E[i]); 
		//vri.pb(E[i] + 1); 
	}
	
	sort(vri.begin(), vri.end());
	vri.erase(unique(vri.begin(), vri.end()), vri.end());  
	
	for(int i = 0; i < (int) vri.size(); i++) mp[vri[i]] = i; 
	
	for(int i = 0; i < n; i++) {
		S[i] = mp[S[i]]; 
		E[i] = mp[E[i]]; 
		//printf("Si = %d Ei = %d\n", S[i] + 1, E[i] + 1);
		sweep.pb(i); 
	}

	sort(sweep.begin(), sweep.end(), comp); 

	for(int i : sweep) {
		up[i][0] = query(S[i], E[i] + 1); 
		update(E[i], i); 
		if(S[i] <= S[up[i][0]]) up[i][0] = -1;
		//printf("UP%d = %d\n", i, up[i][0]);
	}

	for(int i = 0; i < n; i++)
		for(int j = 1; j < LOG; j++)
			if(up[i][j - 1] != -1) up[i][j] = up[up[i][j - 1]][j - 1]; 

	for(int i = 0; i < t; i++) {
		int s, e; 
		scanf("%d%d", &s, &e); 
		//printf("%d %d\n", s, e);
		s--; 
		e--; 
		if(e == s) {
			printf("0\n");
		} else if(E[e] < E[s]) {
			printf("impossible\n");  
		} else {
			pii r = climb(s, e); 
			if(S[r.X] <= E[s] && E[s] <= E[r.X]) printf("%d\n", r.Y + 1); 
			else printf("impossible\n");
		}
	}
	return 0; 
}

Compilation message

events.cpp:5:22: warning: extra tokens at end of #include directive
    5 | #include <algorithm> a#include <cstdio>
      |                      ^
events.cpp:139:11: error: redefinition of 'const int LOG'
  139 | const int LOG = 18;
      |           ^~~
events.cpp:21:11: note: 'const int LOG' previously defined here
   21 | const int LOG = 18;
      |           ^~~
events.cpp:140:11: error: redefinition of 'const int OFF'
  140 | const int OFF = 1 << LOG;
      |           ^~~
events.cpp:22:11: note: 'const int OFF' previously defined here
   22 | const int OFF = 1 << LOG;
      |           ^~~
events.cpp:142:5: error: redefinition of 'int n'
  142 | int n, t;
      |     ^
events.cpp:24:5: note: 'int n' previously declared here
   24 | int n, t;
      |     ^
events.cpp:142:8: error: redefinition of 'int t'
  142 | int n, t;
      |        ^
events.cpp:24:8: note: 'int t' previously declared here
   24 | int n, t;
      |        ^
events.cpp:143:5: error: redefinition of 'int S [262144]'
  143 | int S[OFF], E[OFF], up[OFF][LOG], T[2 * OFF];
      |     ^
events.cpp:25:5: note: 'int S [262144]' previously declared here
   25 | int S[OFF], E[OFF], up[OFF][LOG], T[2 * OFF];
      |     ^
events.cpp:143:13: error: redefinition of 'int E [262144]'
  143 | int S[OFF], E[OFF], up[OFF][LOG], T[2 * OFF];
      |             ^
events.cpp:25:13: note: 'int E [262144]' previously declared here
   25 | int S[OFF], E[OFF], up[OFF][LOG], T[2 * OFF];
      |             ^
events.cpp:143:21: error: redefinition of 'int up [262144][18]'
  143 | int S[OFF], E[OFF], up[OFF][LOG], T[2 * OFF];
      |                     ^~
events.cpp:25:21: note: 'int up [262144][18]' previously declared here
   25 | int S[OFF], E[OFF], up[OFF][LOG], T[2 * OFF];
      |                     ^~
events.cpp:143:35: error: redefinition of 'int T [524288]'
  143 | int S[OFF], E[OFF], up[OFF][LOG], T[2 * OFF];
      |                                   ^
events.cpp:25:35: note: 'int T [524288]' previously declared here
   25 | int S[OFF], E[OFF], up[OFF][LOG], T[2 * OFF];
      |                                   ^
events.cpp:145:13: error: redefinition of 'std::vector<int> vri'
  145 | vector<int> vri, sweep;
      |             ^~~
events.cpp:27:13: note: 'std::vector<int> vri' previously declared here
   27 | vector<int> vri, sweep;
      |             ^~~
events.cpp:145:18: error: redefinition of 'std::vector<int> sweep'
  145 | vector<int> vri, sweep;
      |                  ^~~~~
events.cpp:27:18: note: 'std::vector<int> sweep' previously declared here
   27 | vector<int> vri, sweep;
      |                  ^~~~~
events.cpp:146:15: error: redefinition of 'std::map<int, int> mp'
  146 | map<int, int> mp;
      |               ^~
events.cpp:28:15: note: 'std::map<int, int> mp' previously declared here
   28 | map<int, int> mp;
      |               ^~
events.cpp:148:5: error: redefinition of 'int merge(int, int)'
  148 | int merge(int a, int b) {
      |     ^~~~~
events.cpp:30:5: note: 'int merge(int, int)' previously defined here
   30 | int merge(int a, int b) {
      |     ^~~~~
events.cpp:153:6: error: redefinition of 'void update(int, int)'
  153 | void update(int a, int val) {
      |      ^~~~~~
events.cpp:35:6: note: 'void update(int, int)' previously defined here
   35 | void update(int a, int val) {
      |      ^~~~~~
events.cpp:163:5: error: redefinition of 'int query(int, int, int, int, int)'
  163 | int query(int l, int r, int lo = 0, int hi = OFF, int x = 1) {
      |     ^~~~~
events.cpp:45:5: note: 'int query(int, int, int, int, int)' previously defined here
   45 | int query(int l, int r, int lo = 0, int hi = OFF, int x = 1) {
      |     ^~~~~
events.cpp:170:6: error: redefinition of 'bool comp(int, int)'
  170 | bool comp(int a, int b) {
      |      ^~~~
events.cpp:52:6: note: 'bool comp(int, int)' previously defined here
   52 | bool comp(int a, int b) {
      |      ^~~~
events.cpp:174:5: error: redefinition of 'pii climb(int, int)'
  174 | pii climb(int a, int b) {
      |     ^~~~~
events.cpp:56:5: note: 'pii climb(int, int)' previously defined here
   56 | pii climb(int a, int b) {
      |     ^~~~~
events.cpp:190:5: error: redefinition of 'int main()'
  190 | int main() {
      |     ^~~~
events.cpp:72:5: note: 'int main()' previously defined here
   72 | int main() {
      |     ^~~~
events.cpp: In function 'int main()':
events.cpp:76:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |  scanf("%d%d", &n, &t);
      |  ~~~~~^~~~~~~~~~~~~~~~
events.cpp:78:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |   scanf("%d%d", S + i, E + i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
events.cpp:111:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |   scanf("%d%d", &s, &e);
      |   ~~~~~^~~~~~~~~~~~~~~~
events.cpp: In function 'int main()':
events.cpp:194:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  194 |  scanf("%d%d", &n, &t);
      |  ~~~~~^~~~~~~~~~~~~~~~
events.cpp:196:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  196 |   scanf("%d%d", S + i, E + i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
events.cpp:229:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  229 |   scanf("%d%d", &s, &e);
      |   ~~~~~^~~~~~~~~~~~~~~~