| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 494488 |
2021-12-15T14:47:48 Z |
8e7 |
Circus (Balkan15_CIRCUS) |
C++17 |
|
84 ms |
4612 KB |
//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;
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];
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("found", cur.ss, cur.ff);
auto add = [&] (int x, int val) {
if (val < d[x]) {
d[x] = val;
pq.push({d[x], x});
}
};
int ind = upper_bound(p, p + n, p[cur.ss] - d[cur.ss]) - p - 1;
if (ind >= 0) {
suf.modify(maxn - 2 - ind, p[cur.ss]);
add(ind, suf.query(maxn - 2 - ind) - p[ind]);
}
ind = lower_bound(p, p + n, p[cur.ss] + d[cur.ss]) - p;
if (ind < n) {
pref.modify(ind, -p[cur.ss]);
add(ind, pref.query(ind) + p[ind]);
}
if (cur.ss > 0) {
add(cur.ss-1, min(suf.query(maxn - cur.ss - 1) - p[cur.ss-1], pref.query(cur.ss-1) + p[cur.ss-1]));
}
if (cur.ss < n - 1) {
add(cur.ss+1, min(suf.query(maxn - 3 - cur.ss) - p[cur.ss+1], pref.query(cur.ss+1) + p[cur.ss+1]));
}
}
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
circus.cpp: In function 'int minLength(int)':
circus.cpp:111: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]
111 | 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);
| ~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
84 ms |
4568 KB |
Output is correct |
| 2 |
Correct |
75 ms |
4604 KB |
Output is correct |
| 3 |
Correct |
78 ms |
4612 KB |
Output is correct |
| 4 |
Correct |
78 ms |
4584 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
84 ms |
4568 KB |
Output is correct |
| 2 |
Correct |
75 ms |
4604 KB |
Output is correct |
| 3 |
Correct |
78 ms |
4612 KB |
Output is correct |
| 4 |
Correct |
78 ms |
4584 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
1100 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
84 ms |
4568 KB |
Output is correct |
| 2 |
Correct |
75 ms |
4604 KB |
Output is correct |
| 3 |
Correct |
78 ms |
4612 KB |
Output is correct |
| 4 |
Correct |
78 ms |
4584 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
1100 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
