Submission #494665

#	Time	Username	Problem	Language	Result	Execution time	Memory
494665		8e7	Circus (Balkan15_CIRCUS)	C++17	100 / 100	740 ms	25408 KiB

circus

//Challenge: Accepted
#include "circus.h"
#pragma GCC optimize("Ofast")
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <bitset>
#include <set>
#include <queue>
#include <stack>
#include <assert.h>
#include <cmath>
#include <iomanip>
#include <random>
#include <unordered_map>
#include <chrono>
using namespace std;
void debug(){cout << endl;};
template<class T, class ...U> void debug(T a, U ... b){cout << a << " ", debug(b ...);};
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
};
#define ll long long
#define ld long double
#define maxn 100005
#define mod 998244353
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const int inf = 1<<30;
struct BIT{
	int bit[maxn];
	void init() {
		for (int i = 0;i < maxn;i++) bit[i] = inf;
	}
	void modify(int ind, int val) {
		ind++;
		for (;ind < maxn;ind += ind & (-ind)) bit[ind] = min(bit[ind], val);
	}
	int query(int ind) {
		ind++;
		int ret = inf;
		for (;ind > 0;ind -= ind & (-ind)) ret = min(ret, bit[ind]);
		return ret;
	}
} pref, suf;
int N, M;
int d[maxn], P[maxn];
priority_queue<pii, vector<pii>, greater<pii> > pq;	
set<pii> se;
vector<pii> front, back;
vector<int> fval, bval;
void init(int n, int m, int p[]){
	sort(p, p + n);
	for (int i = 0;i < n;i++) {
		d[i] = inf, P[i] = p[i];	
		if (i < n - 1) se.insert({p[i], i});
	}
	pref.init(), suf.init();
	suf.modify(maxn - n - 2, m), pref.modify(n, -m);
	pq.push({m - p[n-1], n-1});
	d[n-1] = m - p[n-1];
	while (pq.size()) {
		pii cur = pq.top();pq.pop();
		if (cur.ff != d[cur.ss]) continue;
		//debug(cur.ss);	
		if (se.find({p[cur.ss], cur.ss}) != se.end()) {
			se.erase(se.find({p[cur.ss], cur.ss}));	
		}
		//debug("found", cur.ss, cur.ff);
		auto add = [&] (int x) {
			int val = min(suf.query(maxn - 2 - x) - p[x], pref.query(x) + p[x]);
			if (val < d[x]) {
				d[x] = val;
				pq.push({d[x], x});
			}
		};
		auto ind = se.upper_bound({p[cur.ss] - d[cur.ss], inf});
			
		if (ind != se.begin()) {
			ind = prev(ind);
			int id = ind->ss;
			suf.modify(maxn - 2 - id, p[cur.ss]);
			add(id);	
		}
		ind = se.lower_bound({p[cur.ss] + d[cur.ss], 0});
		if (ind != se.end()) {
			int id = ind->ss;
			pref.modify(id, -p[cur.ss]);
			add(id);
		}
		/*
		for (int i = 0;i < n;i++) {
					}
		*/
		ind = se.lower_bound({p[cur.ss], 0});
		if (ind != se.end()) add(ind->ss);
		ind = se.upper_bound({p[cur.ss], inf});
		
		if (ind != se.begin()) add((prev(ind))->ss);
		
	}
	for (int i = 0;i < n;i++) {
		back.push_back({p[i] - d[i], p[i]});	
		front.push_back({p[i] + d[i], p[i]});
	}
	sort(back.begin(), back.end()), sort(front.begin(), front.end());
	fval.resize(n), bval.resize(n);
	int cur = inf;
	for (int i = n - 1;i >= 0;i--) {
		cur = min(cur, back[i].ss);
		bval[i] = cur;
	}
	N = n, M = m;
	cur = 0;
	for (int i = 0;i < n;i++) {
		cur = max(cur, front[i].ss);
		fval[i] = cur;
	}
}
int minLength(int x) {
	int ind = lower_bound(back.begin(), back.end(), make_pair(x, -1)) - back.begin();
	int ans = M - x;
	if (ind < front.size()) ans = min(ans, bval[ind] - x);	
	ind = upper_bound(front.begin(), front.end(), make_pair(x, inf)) - front.begin() - 1;
	if (ind >= 0) ans = min(ans, x - fval[ind]);
	/*
	int ans = M - x;
	for (int i = 0;i < N;i++) {
		if (P[i] + d[i] <= x || P[i] - d[i] >= x) ans = min(ans, abs(P[i] - x));
	}
	*/
	return ans;
}
/*
6 15
1 3 4 7 8 11
 
4 20
3 8 13 18
1
10
*/

Compilation message (stderr)

circus.cpp: In function 'int minLength(int)':
circus.cpp:127:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |  if (ind < front.size()) ans = min(ans, bval[ind] - x);
      |      ~~~~^~~~~~~~~~~~~~
grader.cpp: In function 'int main()':
grader.cpp:14:12: warning: unused variable 'max_code' [-Wunused-variable]
   14 |  long long max_code;
      |            ^~~~~~~~
grader.cpp:16:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |  scanf("%d%d", &N, &M);
      |  ~~~~~^~~~~~~~~~~~~~~~
grader.cpp:18:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |   scanf("%d", &P[i]);
      |   ~~~~~^~~~~~~~~~~~~
grader.cpp:21:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |  scanf("%d", &Q);
      |  ~~~~~^~~~~~~~~~
grader.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |   scanf("%d", &d);
      |   ~~~~~^~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 17 / 17
• Subtask 3: 23 / 23
• Subtask 4: 9 / 9
• Subtask 5: 31 / 31
• Subtask 6: 9 / 9