Submission #761846

#	Time	Username	Problem	Language	Result	Execution time	Memory
761846		gun_gan	Teleporters (IOI08_teleporters)	C++17	10 / 100	415 ms	40308 KiB

teleporters

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MX = 1e6 + 5;

int N, M;
int cnt[MX];

vector<array<int,3>> v;

int main() {
      ios_base::sync_with_stdio(0); cin.tie(0);

      cin >> N >> M;
      for(int i = 0; i < N; i++) {
            int l, r;
            cin >> l >> r;

            v.push_back({l, r, i});
            v.push_back({r, l, i});
      }

      sort(v.begin(), v.end());

      int cur = 0;
      while(1) {
            array<int,3> arr = {cur + 1, 0, 0};
            auto nxt = lower_bound(v.begin(), v.end(), arr);

            // cout << cur << " -> " << (*nxt)[1] << '\n';
            if(nxt == v.end()) break;

            cur = (*nxt)[1];
            cnt[(*nxt)[2]]++;
      }

      ll ans = 0, x = 0, y = 0;
      for(int i = 0; i < N; i++) {
            if(cnt[i] == 2) {
                  ans += 2;
            } else if(cnt[i] == 1) {
                  x++;
                  ans += 1;
            } else { 
                  y++;
            }
      }

      while(x > 0 && M > 0) {
            x--;
            ans++;
            M--;
            ans += 2;

            if(y > 0) {
                  x++;
                  y--;
                  ans++;
            }
      }

      if(y > 0 && M > 0) {
            ll m = min(y, 1ll * M);
            ans += 2 * m;
            y -= m;
            M -= m;
      }

      while(M - 2 >= 0) {
            M -= 2;
            ans += 4;
      }

      ans += M & 1;
      cout << ans << '\n';
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 5
• Subtask 3: 5 / 5
• Subtask 4: 0 / 5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 5
• Subtask 10: 0 / 5
• Subtask 11: 0 / 5
• Subtask 12: 0 / 5
• Subtask 13: 0 / 5
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5
• Subtask 20: 0 / 5