| # |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
| 56923 |
2018-07-13T08:02:31 Z |
강태규(#1633) |
방벽 (JOI15_walls) |
C++11 |
|
36 ms |
2408 KB |
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>
#define XXX printf("Big Rigs - OVER THE ROAD RACING\n")
using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;
int n, m, k;
struct manager {
int st;
map<int, int> pos;
set<pii> dist;
llong sum = 0;
void insert(int i, int x) {
pos[i] = x;
if (x < 0) x = -x;
sum += x;
dist.emplace(x, i);
}
void erase(int i) {
int x = pos[i];
pos.erase(i);
if (x < 0) x = -x;
sum -= x;
dist.erase(pii(x, i));
}
bool process(int x) {
if (pos.size() < 2) return 0;
if (x < dist.begin()->first) return 0;
int d, i;
tie(d, i) = *(dist.begin());
map<int, int>::iterator it, pr, nx;
it = pos.find(i);
if (it == pos.begin()) {
st += it->second;
erase(i);
}
else if (it == --pos.end()) {
erase(i);
}
else {
pr = it;
nx = it;
--pr;
++nx;
d += pr->second + nx->second;
erase(i);
erase(pr->first);
erase(nx->first);
insert(i, d);
}
return 1;
}
int size() const {
return pos.size();
}
} mg;
struct wall {
int a, b, i;
void scan(int idx) {
scanf("%d%d", &a, &b);
i = idx;
}
bool operator<(const wall &x) const {
return b - a < x.b - x.a;
}
} walls[200000];
llong ans[200000];
int moveWall(int &a, int &b, int p) {
if (p < a) {
p = a - p;
a -= p;
b -= p;
return p;
}
if (b < p) {
p = p - b;
a += p;
b += p;
return p;
}
return 0;
}
int laser[200000];
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < n; ++i) {
walls[i].scan(i);
}
for (int i = 0; i < m; ++i) {
scanf("%d", laser + i);
}
k = 0;
for (int i = 0; i < m; ++i) {
if (k > 0 && laser[k - 1] == laser[i]) continue;
if (k > 1 && (laser[k - 2] < laser[k - 1]) == (laser[k - 1] < laser[i]))
--k;
laser[k++] = laser[i];
}
if (k == 1) {
int p = laser[0];
for (int i = 0; i < n; ++i) {
printf("%d\n", moveWall(walls[i].a, walls[i].b, p));
}
return 0;
}
mg.st = laser[0];
sort(walls, walls + n);
for (int i = 1; i < k; ++i) mg.insert(i, laser[i] - laser[i - 1]);
for (int i = 0; i < n; ++i) {
int a = walls[i].a;
int b = walls[i].b;
llong &ret = ans[walls[i].i];
while (mg.process(b - a));
if (mg.size() < 2) {
ret += moveWall(a, b, mg.st);
ret += moveWall(a, b, mg.st + mg.pos.begin()->second);
continue;
}
if (mg.pos.begin()->second < 0) ret = abs(mg.st - b);
else ret = abs(mg.st - a);
ret += mg.sum;
ret -= (llong)mg.size() * (b - a);
}
for (int i = 0; i < n; ++i) {
printf("%lld\n", ans[i]);
}
return 0;
}
Compilation message
walls.cpp: In function 'int main()':
walls.cpp:105:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~
walls.cpp:110:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", laser + i);
~~~~~^~~~~~~~~~~~~~~~~
walls.cpp: In member function 'void wall::scan(int)':
walls.cpp:78:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &a, &b);
~~~~~^~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
8 ms |
1016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
36 ms |
2408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
8 ms |
1016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
