oj.uz

Submission #282601

# Submission time Handle Problem Language Result Execution time Memory
282601 2020-08-24T15:28:36 Z imeimi2000 None (JOI15_walls) C++17
100 / 100
 862 ms 32632 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]
  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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1152 KB Output is correct
2 Correct 351 ms 15604 KB Output is correct
3 Correct 573 ms 21880 KB Output is correct
4 Correct 543 ms 21860 KB Output is correct
5 Correct 591 ms 21820 KB Output is correct
6 Correct 367 ms 21880 KB Output is correct
7 Correct 34 ms 2808 KB Output is correct
8 Correct 44 ms 3064 KB Output is correct

Subtask #2
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 2792 KB Output is correct
2 Correct 478 ms 16484 KB Output is correct
3 Correct 136 ms 10836 KB Output is correct
4 Correct 862 ms 31000 KB Output is correct
5 Correct 563 ms 24700 KB Output is correct
6 Correct 824 ms 31096 KB Output is correct
7 Correct 563 ms 24824 KB Output is correct
8 Correct 837 ms 30968 KB Output is correct
9 Correct 104 ms 8568 KB Output is correct
10 Correct 358 ms 30140 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1152 KB Output is correct
2 Correct 351 ms 15604 KB Output is correct
3 Correct 573 ms 21880 KB Output is correct
4 Correct 543 ms 21860 KB Output is correct
5 Correct 591 ms 21820 KB Output is correct
6 Correct 367 ms 21880 KB Output is correct
7 Correct 34 ms 2808 KB Output is correct
8 Correct 44 ms 3064 KB Output is correct
9 Correct 36 ms 2792 KB Output is correct
10 Correct 478 ms 16484 KB Output is correct
11 Correct 136 ms 10836 KB Output is correct
12 Correct 862 ms 31000 KB Output is correct
13 Correct 563 ms 24700 KB Output is correct
14 Correct 824 ms 31096 KB Output is correct
15 Correct 563 ms 24824 KB Output is correct
16 Correct 837 ms 30968 KB Output is correct
17 Correct 104 ms 8568 KB Output is correct
18 Correct 358 ms 30140 KB Output is correct
19 Correct 555 ms 26488 KB Output is correct
20 Correct 849 ms 32632 KB Output is correct
21 Correct 555 ms 26356 KB Output is correct
22 Correct 738 ms 29792 KB Output is correct
23 Correct 557 ms 26232 KB Output is correct
24 Correct 839 ms 32488 KB Output is correct
25 Correct 132 ms 10872 KB Output is correct
26 Correct 181 ms 13048 KB Output is correct
27 Correct 404 ms 32120 KB Output is correct