Submission #282601

#	Time	Username	Problem	Language	Result	Execution time	Memory
282601		imeimi2000	방벽 (JOI15_walls)	C++17	100 / 100	862 ms	32632 KiB

walls

#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 + it->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 (stderr)

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]
  105 |     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]
  110 |         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]
   78 |         scanf("%d%d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 45 / 45
• Subtask 3: 45 / 45