oj.uz

Submission #56925

# Submission time Handle Problem Language Result Execution time Memory
56925 2018-07-13T08:09:54 Z 강태규(#1633) None (JOI15_walls) C++11
100 / 100
 1036 ms 78848 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 + 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

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);
         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1016 KB Output is correct
2 Correct 386 ms 13804 KB Output is correct
3 Correct 656 ms 20016 KB Output is correct
4 Correct 632 ms 20032 KB Output is correct
5 Correct 549 ms 20144 KB Output is correct
6 Correct 360 ms 20156 KB Output is correct
7 Correct 30 ms 20156 KB Output is correct
8 Correct 37 ms 20156 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 20156 KB Output is correct
2 Correct 573 ms 20156 KB Output is correct
3 Correct 137 ms 20156 KB Output is correct
4 Correct 1036 ms 27036 KB Output is correct
5 Correct 587 ms 27036 KB Output is correct
6 Correct 877 ms 27036 KB Output is correct
7 Correct 558 ms 27036 KB Output is correct
8 Correct 873 ms 27052 KB Output is correct
9 Correct 103 ms 27052 KB Output is correct
10 Correct 380 ms 27052 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1016 KB Output is correct
2 Correct 386 ms 13804 KB Output is correct
3 Correct 656 ms 20016 KB Output is correct
4 Correct 632 ms 20032 KB Output is correct
5 Correct 549 ms 20144 KB Output is correct
6 Correct 360 ms 20156 KB Output is correct
7 Correct 30 ms 20156 KB Output is correct
8 Correct 37 ms 20156 KB Output is correct
9 Correct 37 ms 20156 KB Output is correct
10 Correct 573 ms 20156 KB Output is correct
11 Correct 137 ms 20156 KB Output is correct
12 Correct 1036 ms 27036 KB Output is correct
13 Correct 587 ms 27036 KB Output is correct
14 Correct 877 ms 27036 KB Output is correct
15 Correct 558 ms 27036 KB Output is correct
16 Correct 873 ms 27052 KB Output is correct
17 Correct 103 ms 27052 KB Output is correct
18 Correct 380 ms 27052 KB Output is correct
19 Correct 587 ms 27052 KB Output is correct
20 Correct 860 ms 38652 KB Output is correct
21 Correct 575 ms 38652 KB Output is correct
22 Correct 898 ms 47760 KB Output is correct
23 Correct 561 ms 49520 KB Output is correct
24 Correct 896 ms 61724 KB Output is correct
25 Correct 129 ms 61724 KB Output is correct
26 Correct 157 ms 61724 KB Output is correct
27 Correct 437 ms 78848 KB Output is correct