Submission #56306663


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define PB push_back
#define FS first
#define SD second
#define ary(k) array<int, k>
template <class A, class B> void cmx(A &x, B y) { x = max<A>(x, y); }
template <class A, class B> void cmn(A &x, B y) { x = min<A>(x, y); }
typedef pair<int, int> pii;
typedef vector<int> vi;
signed main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
int n, m;
cin >> n >> m;
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define PB push_back
#define FS first
#define SD second
#define ary(k) array<int, k>
template <class A, class B> void cmx(A &x, B y) { x = max<A>(x, y); }
template <class A, class B> void cmn(A &x, B y) { x = min<A>(x, y); }
typedef pair<int, int> pii;
typedef vector<int> vi;

signed main() {
  cin.tie(0)->sync_with_stdio(0);
  cin.exceptions(cin.failbit);
  int n, m;
  cin >> n >> m;
  vector<vector<ary(2)>> in(n);
  vi lstl(n, -1);
  rep(i, 0, m) {
    int t, p;
    cin >> t >> p;
    p--;
    if (lstl[p] == -1)
      lstl[p] = t;
    else
      in[p].PB({lstl[p], t}), lstl[p] = -1;
  }
  const int B = 450;
  auto isect = [&](int l, int r, int x, int y) {
    return pii{max(l, x), min(r, y)};
  };
  auto calc_small = [&](int a, int b) {
    int ans = 0, ptr = 0;
    vi lft(sz(in[a]));
    rep(i, 0, sz(in[a])) {
      auto [l, r] = in[a][i];
      while (ptr < sz(in[b]) && in[b][ptr][1] < l) {
        ptr++;
      }
      lft[i] = ptr;
    }
    ptr = -1;
    vi rit(sz(in[a]));
    rep(i, 0, sz(in[a])) {
      auto [l, r] = in[a][i];
      while (ptr + 1 < sz(in[b]) && in[b][ptr + 1][0] <= r)
        ptr++;
      rit[i] = ptr;
    }
    rep(i, 0, sz(in[a])) {
      rep(j, lft[i], rit[i] + 1) {
        auto [l, r] = isect(in[a][i][0], in[a][i][1], in[b][j][0], in[b][j][1]);
        ans += max(0ll, r - l);
      }
    }
    return ans;
  };

  int q;
  cin >> q;
  vi ans(q);
  vector<vector<ary(2)>> off(n);
  rep(i, 0, q) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    if (sz(in[a]) > B) {
      off[a].PB({b, i});
    } else if (sz(in[b]) > B) {
      off[b].PB({a, i});
    } else {
      ans[i] = calc_small(a, b);
    }
  }
  auto calc_big = [&](int b) {
    vi cum(n);
    rep(i, 0, n) { cum[i] = calc_small(i, b); }
    for (auto [a, i] : off[b])
      ans[i] = cum[a];
  };
  rep(i, 0, n) if (sz(in[i]) > B) { calc_big(i); }
  rep(i, 0, q) cout << ans[i] << "\n";
}

Submission Info

Submission Time
Task G - AtCoder Office
User thomas_li
Language C++ 20 (gcc 12.2)
Score 575
Code Size 2191 Byte
Status AC
Exec Time 3695 ms
Memory 23500 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 575 / 575
Status
AC × 2
AC × 78
Set Name Test Cases
Sample 00_sample_00.txt, 00_sample_01.txt
All 00_sample_00.txt, 00_sample_01.txt, 01_random_02.txt, 01_random_03.txt, 01_random_04.txt, 01_random_05.txt, 01_random_06.txt, 01_random_07.txt, 01_random_08.txt, 01_random_09.txt, 01_random_10.txt, 01_random_11.txt, 01_random_12.txt, 01_random_13.txt, 01_random_14.txt, 01_random_15.txt, 01_random_16.txt, 01_random_17.txt, 01_random_18.txt, 01_random_19.txt, 01_random_20.txt, 01_random_21.txt, 01_random_22.txt, 01_random_23.txt, 01_random_24.txt, 01_random_25.txt, 01_random_26.txt, 01_random_27.txt, 01_random_28.txt, 01_random_29.txt, 01_random_30.txt, 01_random_31.txt, 01_random_32.txt, 01_random_33.txt, 01_random_34.txt, 01_random_35.txt, 01_random_36.txt, 01_random_37.txt, 01_random_38.txt, 01_random_39.txt, 01_random_40.txt, 01_random_41.txt, 01_random_42.txt, 01_random_43.txt, 01_random_44.txt, 01_random_45.txt, 01_random_46.txt, 01_random_47.txt, 01_random_48.txt, 01_random_49.txt, 01_random_50.txt, 01_random_51.txt, 01_random_52.txt, 01_random_53.txt, 01_random_54.txt, 01_random_55.txt, 01_random_56.txt, 01_random_57.txt, 01_random_58.txt, 01_random_59.txt, 01_random_60.txt, 01_random_61.txt, 01_random_62.txt, 01_random_63.txt, 01_random_64.txt, 01_random_65.txt, 01_random_66.txt, 01_random_67.txt, 01_random_68.txt, 01_random_69.txt, 02_handmade_68.txt, 02_handmade_69.txt, 02_handmade_70.txt, 02_handmade_71.txt, 02_handmade_72.txt, 02_handmade_73.txt, 02_handmade_74.txt, 02_handmade_75.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 1 ms 3504 KB
00_sample_01.txt AC 1 ms 3508 KB
01_random_02.txt AC 77 ms 18356 KB
01_random_03.txt AC 75 ms 18444 KB
01_random_04.txt AC 79 ms 18352 KB
01_random_05.txt AC 77 ms 18324 KB
01_random_06.txt AC 86 ms 18284 KB
01_random_07.txt AC 79 ms 18236 KB
01_random_08.txt AC 77 ms 18340 KB
01_random_09.txt AC 79 ms 18308 KB
01_random_10.txt AC 77 ms 18448 KB
01_random_11.txt AC 77 ms 18424 KB
01_random_12.txt AC 87 ms 18452 KB
01_random_13.txt AC 77 ms 18388 KB
01_random_14.txt AC 627 ms 8508 KB
01_random_15.txt AC 19 ms 10152 KB
01_random_16.txt AC 42 ms 7260 KB
01_random_17.txt AC 52 ms 6060 KB
01_random_18.txt AC 47 ms 15956 KB
01_random_19.txt AC 40 ms 8056 KB
01_random_20.txt AC 45 ms 10096 KB
01_random_21.txt AC 40 ms 9988 KB
01_random_22.txt AC 45 ms 10456 KB
01_random_23.txt AC 61 ms 10260 KB
01_random_24.txt AC 136 ms 10700 KB
01_random_25.txt AC 581 ms 9600 KB
01_random_26.txt AC 573 ms 9424 KB
01_random_27.txt AC 665 ms 8364 KB
01_random_28.txt AC 361 ms 7440 KB
01_random_29.txt AC 363 ms 7252 KB
01_random_30.txt AC 125 ms 7524 KB
01_random_31.txt AC 79 ms 8920 KB
01_random_32.txt AC 76 ms 16004 KB
01_random_33.txt AC 43 ms 12676 KB
01_random_34.txt AC 43 ms 11004 KB
01_random_35.txt AC 45 ms 10484 KB
01_random_36.txt AC 62 ms 10272 KB
01_random_37.txt AC 55 ms 11220 KB
01_random_38.txt AC 115 ms 10892 KB
01_random_39.txt AC 123 ms 10452 KB
01_random_40.txt AC 386 ms 10836 KB
01_random_41.txt AC 392 ms 10748 KB
01_random_42.txt AC 606 ms 9676 KB
01_random_43.txt AC 660 ms 7720 KB
01_random_44.txt AC 678 ms 7624 KB
01_random_45.txt AC 205 ms 7692 KB
01_random_46.txt AC 110 ms 8836 KB
01_random_47.txt AC 102 ms 18448 KB
01_random_48.txt AC 3262 ms 13648 KB
01_random_49.txt AC 3669 ms 13980 KB
01_random_50.txt AC 71 ms 13328 KB
01_random_51.txt AC 77 ms 13324 KB
01_random_52.txt AC 71 ms 13296 KB
01_random_53.txt AC 70 ms 13264 KB
01_random_54.txt AC 54 ms 13360 KB
01_random_55.txt AC 57 ms 14748 KB
01_random_56.txt AC 1545 ms 10316 KB
01_random_57.txt AC 1179 ms 9096 KB
01_random_58.txt AC 936 ms 9644 KB
01_random_59.txt AC 807 ms 10212 KB
01_random_60.txt AC 780 ms 10316 KB
01_random_61.txt AC 55 ms 13520 KB
01_random_62.txt AC 56 ms 14072 KB
01_random_63.txt AC 476 ms 9892 KB
01_random_64.txt AC 371 ms 9068 KB
01_random_65.txt AC 305 ms 9388 KB
01_random_66.txt AC 270 ms 9984 KB
01_random_67.txt AC 260 ms 9972 KB
01_random_68.txt AC 57 ms 23500 KB
01_random_69.txt AC 57 ms 23400 KB
02_handmade_68.txt AC 57 ms 23400 KB
02_handmade_69.txt AC 57 ms 23324 KB
02_handmade_70.txt AC 2782 ms 21516 KB
02_handmade_71.txt AC 3684 ms 21220 KB
02_handmade_72.txt AC 2802 ms 21228 KB
02_handmade_73.txt AC 2788 ms 21516 KB
02_handmade_74.txt AC 3695 ms 21140 KB
02_handmade_75.txt AC 2802 ms 21168 KB


2025-01-18 (Sat)
07:12:23 +00:00