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;
#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 |
|
|
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 |