oj.uz

Submission #659011

# Submission time Handle Problem Language Result Execution time Memory
659011 2022-11-15T18:48:35 Z 600Mihnea New Home (APIO18_new_home) C++17
5 / 100
 5000 ms 64048 KB 
bool home = 0;

#include <bits/stdc++.h>

using namespace std;

struct Store {
  int x;
  int type;
  int first_time;
  int last_time;
};

struct Query {
  int x;
  int t;
};

const int N = (int) 3e5 + 7;
int n;
int k;
int q;
vector<int> whereType[N];
Store stores[N];
Query queries[N];
bool negative[N];
vector<int> events;

int getTimeOfEvent(int i) {
  if (i >= 1) {
    assert(1 <= i && i <= n);
    return stores[i].first_time;
  } else {
    i *= -1;
    assert(1 <= i && i <= n);
    return stores[i].last_time + 1;
  }
}

bool cmpEvents(int i, int j) {
  return getTimeOfEvent(i) < getTimeOfEvent(j);
}

struct Position {
  int i;
};

bool operator < (Position a, Position b) {
  int i = a.i, j = b.i;
  if (stores[i].x == stores[j].x) {
    return i < j;
  } else {
    return stores[i].x < stores[j].x;
  }
}

struct Segment {
  int first_time;
  int last_time;
  int x1;
  int x2;
};

struct RelaxSegment {
  int first_time;
  int last_time;
  int limit;
  int x;
};

vector<RelaxSegment> rels[2];

vector<Segment> segments;

void addSegment(int first_time, int last_time, int i, int j) {
  assert(1 <= i && i <= n + 2);
  assert(1 <= j && j <= n + 2);

  if (first_time > last_time) {
    return;
  }

  assert(0 <= first_time && first_time <= last_time && last_time < q);

  assert(stores[i].x <= stores[j].x);

  segments.push_back({first_time, last_time, stores[i].x, stores[j].x});
}

int print[N];

int main() {
  if (home) {
    freopen ("input.txt", "r", stdin);
  } else {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  }
  {
    /// Read
    cin >> n >> k >> q;
    for (int i = 1; i <= n; i++) {
      cin >> stores[i].x >> stores[i].type >> stores[i].first_time >> stores[i].last_time;
    }
    for (int i = 1; i <= q; i++) {
      cin >> queries[i].x >> queries[i].t;
    }
  }
  {
    /// Normalize time
    vector<int> interestingTimes;
    for (int i = 1; i <= q; i++) {
      interestingTimes.push_back(queries[i].t);
    }
    sort(interestingTimes.begin(), interestingTimes.end());
    interestingTimes.resize(unique(interestingTimes.begin(), interestingTimes.end()) - interestingTimes.begin());
    for (int i = 1; i <= q; i++) {
      queries[i].t = lower_bound(interestingTimes.begin(), interestingTimes.end(), queries[i].t) - interestingTimes.begin();
    }
    int y = 0;
    for (int i = 1; i <= n; i++) {
      stores[i].first_time = lower_bound(interestingTimes.begin(), interestingTimes.end(), stores[i].first_time) - interestingTimes.begin();
      stores[i].last_time = lower_bound(interestingTimes.begin(), interestingTimes.end(), stores[i].last_time + 1) - interestingTimes.begin() - 1;
      if (stores[i].first_time <= stores[i].last_time) {
        stores[++y] = stores[i];
      }
    }
    n = y;
  }

  {
    /// Some more computation
    for (int i = 1; i <= n; i++) {
      whereType[stores[i].type].push_back(i);
    }
    stores[n + 1].x = -((int) 1e8 + 7);
    stores[n + 2].x = +((int) 2e8 + 7);
    for (int type = 1; type <= k; type++) {
      set<Position> positions;
      map<pair<int, int>, int> sinceWhen;
      positions.insert({n + 1});
      positions.insert({n + 2});

      sinceWhen[{n + 1, n + 2}] = 0;
      events.clear();
      for (auto &i : whereType[type]) {
        events.push_back(+i);
        events.push_back(-i);
      }
      sort(events.begin(), events.end(), cmpEvents);
      int l_events = 0;
      while (l_events < (int) events.size()) {
        int r_events = l_events;
        while (r_events + 1 < (int) events.size() && getTimeOfEvent(events[r_events + 1]) == getTimeOfEvent(events[r_events])) {
          r_events++;
        }
        int current_time = getTimeOfEvent(events[l_events]);
        for (int iter_events = l_events; iter_events <= r_events; iter_events++) {
          int i = events[iter_events];

          if (i >= 1) {
            assert(1 <= i && i <= n);
            positions.insert({i});


            auto it = positions.find({i});
            assert(it != positions.end());
            auto nxt = it;
            auto ant = it;
            nxt++;
            assert(nxt != positions.end());
            assert(ant != positions.begin());
            ant--;

            addSegment(sinceWhen[{ant->i, nxt->i}], current_time - 1, ant->i, nxt->i);

            assert(sinceWhen.count({ant->i, nxt->i}));
            sinceWhen.erase({ant->i, nxt->i});
            assert(!sinceWhen.count({ant->i, nxt->i}));
            sinceWhen[{ant->i, it->i}] = current_time;
            sinceWhen[{it->i, nxt->i}] = current_time;
          } else {
            i *= -1;
            assert(1 <= i && i <= n);
            assert(positions.count({i}));

            auto it = positions.find({i});
            assert(it != positions.end());
            auto nxt = it;
            auto ant = it;
            nxt++;
            assert(nxt != positions.end());
            assert(ant != positions.begin());
            ant--;

            assert(!sinceWhen.count({ant->i, nxt->i}));
            sinceWhen[{ant->i, nxt->i}] = current_time;
            assert(sinceWhen.count({ant->i, nxt->i}));


            addSegment(sinceWhen[{ant->i, it->i}], current_time - 1, ant->i, it->i);
            assert(sinceWhen.count({ant->i, it->i}));
            sinceWhen.erase({ant->i, it->i});

            addSegment(sinceWhen[{it->i, nxt->i}], current_time - 1, it->i, nxt->i);
            assert(sinceWhen.count({it->i, nxt->i}));
            sinceWhen.erase({it->i, nxt->i});

            positions.erase({i});
          }
        }
        l_events = r_events + 1;
      }
      for (auto &it : sinceWhen) {
        addSegment(it.second, q - 1, it.first.first, it.first.second);
      }
    }
  }
  {
    /// Some other Brute

    for (auto &segment : segments) {
      int t1 = segment.first_time;
      int t2 = segment.last_time;
      int x1 = segment.x1;
      int x2 = segment.x2;

      int xmid = (x1 + x2) / 2;
      int xmid2 = (x1 + x2 + 1) / 2;
      rels[0].push_back({t1, t2, xmid, x1});
      rels[1].push_back({t1, t2, -xmid2, -x2});
    }

    for (int inv = 0; inv <= 1; inv++) {
      vector<RelaxSegment> relaxSegments = rels[inv];

      for (int iq = 1; iq <= q; iq++) {
        for (auto &relaxSegment : relaxSegments) {
          if (relaxSegment.first_time <= queries[iq].t && queries[iq].t <= relaxSegment.last_time) {
            if (queries[iq].x <= relaxSegment.limit) {
              print[iq] = max(print[iq], queries[iq].x - relaxSegment.x);
            }
          }
        }
      }

      for (int iq = 1; iq <= q; iq++) {
        queries[iq].x *= -1;
      }
    }

    for (int iq = 1; iq <= q; iq++) {
      int maxDist = 0;
      for (auto &segment : segments) {
        if (segment.first_time <= queries[iq].t && queries[iq].t <= segment.last_time) {
          if (segment.x1 <= queries[iq].x && queries[iq].x <= segment.x2) {
            maxDist = max(maxDist, min(abs(queries[iq].x - segment.x1), abs(queries[iq].x - segment.x2)));
          }
        }
      }
      assert(maxDist == print[iq]);
      if (maxDist > (int) 1e8) {
        maxDist = -1;
      }
      cout << maxDist << "\n";
    }
    return 0;
    cout << " ----------- \n";
  }
  {
    /// Brute
    for (int iq = 1; iq <= q; iq++) {
      int maxDist = 0;
      for (int t = 1; t <= k; t++) {
        int minDist = (int) 1e9 + 7;
        for (auto &i : whereType[t]) {
          if (stores[i].first_time <= queries[iq].t && queries[iq].t <= stores[i].last_time) {
            minDist = min(minDist, abs(stores[i].x - queries[iq].x));
          }
        }
        maxDist = max(maxDist, minDist);
      }
      if (maxDist == (int) 1e9 + 7) {
        maxDist = -1;
      }
      cout << maxDist << "\n";
    }
  }
  return 0;
}

Compilation message

new_home.cpp: In function 'int main()':
new_home.cpp:94:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |     freopen ("input.txt", "r", stdin);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 5 ms 7380 KB Output is correct
5 Correct 9 ms 7396 KB Output is correct
6 Correct 9 ms 7476 KB Output is correct
7 Correct 9 ms 7536 KB Output is correct
8 Correct 12 ms 7536 KB Output is correct
9 Correct 8 ms 7508 KB Output is correct
10 Correct 9 ms 7508 KB Output is correct
11 Correct 6 ms 7508 KB Output is correct
12 Correct 7 ms 7380 KB Output is correct
13 Correct 6 ms 7380 KB Output is correct
14 Correct 5 ms 7480 KB Output is correct
15 Correct 7 ms 7508 KB Output is correct
16 Correct 7 ms 7536 KB Output is correct
17 Correct 7 ms 7412 KB Output is correct
18 Correct 9 ms 7464 KB Output is correct
19 Correct 9 ms 7540 KB Output is correct
20 Correct 7 ms 7508 KB Output is correct
21 Correct 7 ms 7508 KB Output is correct
22 Correct 7 ms 7508 KB Output is correct
23 Correct 10 ms 7536 KB Output is correct
24 Correct 9 ms 7532 KB Output is correct
25 Correct 8 ms 7508 KB Output is correct
26 Correct 5 ms 7508 KB Output is correct
27 Correct 7 ms 7508 KB Output is correct
28 Correct 6 ms 7508 KB Output is correct
29 Correct 5 ms 7380 KB Output is correct
30 Correct 5 ms 7380 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 5 ms 7380 KB Output is correct
5 Correct 9 ms 7396 KB Output is correct
6 Correct 9 ms 7476 KB Output is correct
7 Correct 9 ms 7536 KB Output is correct
8 Correct 12 ms 7536 KB Output is correct
9 Correct 8 ms 7508 KB Output is correct
10 Correct 9 ms 7508 KB Output is correct
11 Correct 6 ms 7508 KB Output is correct
12 Correct 7 ms 7380 KB Output is correct
13 Correct 6 ms 7380 KB Output is correct
14 Correct 5 ms 7480 KB Output is correct
15 Correct 7 ms 7508 KB Output is correct
16 Correct 7 ms 7536 KB Output is correct
17 Correct 7 ms 7412 KB Output is correct
18 Correct 9 ms 7464 KB Output is correct
19 Correct 9 ms 7540 KB Output is correct
20 Correct 7 ms 7508 KB Output is correct
21 Correct 7 ms 7508 KB Output is correct
22 Correct 7 ms 7508 KB Output is correct
23 Correct 10 ms 7536 KB Output is correct
24 Correct 9 ms 7532 KB Output is correct
25 Correct 8 ms 7508 KB Output is correct
26 Correct 5 ms 7508 KB Output is correct
27 Correct 7 ms 7508 KB Output is correct
28 Correct 6 ms 7508 KB Output is correct
29 Correct 5 ms 7380 KB Output is correct
30 Correct 5 ms 7380 KB Output is correct
31 Execution timed out 5036 ms 21624 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5066 ms 50856 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5060 ms 64048 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 5 ms 7380 KB Output is correct
5 Correct 9 ms 7396 KB Output is correct
6 Correct 9 ms 7476 KB Output is correct
7 Correct 9 ms 7536 KB Output is correct
8 Correct 12 ms 7536 KB Output is correct
9 Correct 8 ms 7508 KB Output is correct
10 Correct 9 ms 7508 KB Output is correct
11 Correct 6 ms 7508 KB Output is correct
12 Correct 7 ms 7380 KB Output is correct
13 Correct 6 ms 7380 KB Output is correct
14 Correct 5 ms 7480 KB Output is correct
15 Correct 7 ms 7508 KB Output is correct
16 Correct 7 ms 7536 KB Output is correct
17 Correct 7 ms 7412 KB Output is correct
18 Correct 9 ms 7464 KB Output is correct
19 Correct 9 ms 7540 KB Output is correct
20 Correct 7 ms 7508 KB Output is correct
21 Correct 7 ms 7508 KB Output is correct
22 Correct 7 ms 7508 KB Output is correct
23 Correct 10 ms 7536 KB Output is correct
24 Correct 9 ms 7532 KB Output is correct
25 Correct 8 ms 7508 KB Output is correct
26 Correct 5 ms 7508 KB Output is correct
27 Correct 7 ms 7508 KB Output is correct
28 Correct 6 ms 7508 KB Output is correct
29 Correct 5 ms 7380 KB Output is correct
30 Correct 5 ms 7380 KB Output is correct
31 Execution timed out 5036 ms 21624 KB Time limit exceeded
32 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 5 ms 7380 KB Output is correct
5 Correct 9 ms 7396 KB Output is correct
6 Correct 9 ms 7476 KB Output is correct
7 Correct 9 ms 7536 KB Output is correct
8 Correct 12 ms 7536 KB Output is correct
9 Correct 8 ms 7508 KB Output is correct
10 Correct 9 ms 7508 KB Output is correct
11 Correct 6 ms 7508 KB Output is correct
12 Correct 7 ms 7380 KB Output is correct
13 Correct 6 ms 7380 KB Output is correct
14 Correct 5 ms 7480 KB Output is correct
15 Correct 7 ms 7508 KB Output is correct
16 Correct 7 ms 7536 KB Output is correct
17 Correct 7 ms 7412 KB Output is correct
18 Correct 9 ms 7464 KB Output is correct
19 Correct 9 ms 7540 KB Output is correct
20 Correct 7 ms 7508 KB Output is correct
21 Correct 7 ms 7508 KB Output is correct
22 Correct 7 ms 7508 KB Output is correct
23 Correct 10 ms 7536 KB Output is correct
24 Correct 9 ms 7532 KB Output is correct
25 Correct 8 ms 7508 KB Output is correct
26 Correct 5 ms 7508 KB Output is correct
27 Correct 7 ms 7508 KB Output is correct
28 Correct 6 ms 7508 KB Output is correct
29 Correct 5 ms 7380 KB Output is correct
30 Correct 5 ms 7380 KB Output is correct
31 Execution timed out 5036 ms 21624 KB Time limit exceeded
32 Halted 0 ms 0 KB -