Submission #494415

#	Time	Username	Problem	Language	Result	Execution time	Memory
494415		8e7	Circus (Balkan15_CIRCUS)	C++17	11 / 100	47 ms	3560 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 = maxn - 1 - ind;
		for (;ind < maxn;ind += ind & (-ind)) bit[ind] = min(bit[ind], val);
	}
	int query(int ind) {
		ind = maxn - 1 - ind;
		int ret = inf;
		for (;ind > 0;ind -= ind & (-ind)) ret = min(ret, bit[ind]);
		return ret;
	}
} b;
int M;
int d[maxn];
priority_queue<pii, vector<pii>, greater<pii> > pq;	
vector<pii> pnt;
vector<int> mi;
void init(int n, int m, int p[]){
	sort(p, p + n);
	for (int i = 0;i < n;i++) d[i] = inf;	
	b.init();
	b.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;
		int ind = upper_bound(p, p + n, p[cur.ss] - d[cur.ss]) - p - 1;
		auto add = [&] (int x) {
			int val = b.query(x) - p[x];
			if (val < d[x]) {
				d[x] = val;
				pq.push({d[x], x});
			}
		};
		if (ind >= 0) {
			b.modify(ind, p[cur.ss]);
			add(ind);	
		}
		if (cur.ss > 0) {
			add(cur.ss-1);
		}
	}
	for (int i = 0;i < n;i++) {
		pnt.push_back({p[i] - d[i], p[i]});	
	}
	sort(pnt.begin(), pnt.end());
	mi.resize(n);
	int cur = inf;
	for (int i = n - 1;i >= 0;i--) {
		//debug("pnt", pnt[i].ff, pnt[i].ss);
		cur = min(cur, pnt[i].ss);
		mi[i] = cur;
	}
	M = m;
}
int minLength(int x) {
	int ind = lower_bound(pnt.begin(), pnt.end(), make_pair(x, 0)) - pnt.begin();
	int ans = M - x;
	if (ind < pnt.size()) ans = min(ans, mi[ind] - x);	
	return ans;
}
/*
3 8
0
3
6
2
4
5
*/

Compilation message (stderr)

circus.cpp: In function 'int minLength(int)':
circus.cpp:97: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]
   97 |  if (ind < pnt.size()) ans = min(ans, mi[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: 0 / 17
• Subtask 3: 0 / 23
• Subtask 4: 0 / 9
• Subtask 5: 0 / 31
• Subtask 6: 0 / 9