QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#462491 | #8535. Mooball Teams III | zlxFTH | 100 ✓ | 762ms | 21084kb | C++14 | 4.5kb | 2024-07-03 20:16:24 | 2024-07-03 20:16:26 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr int P = 1e9 + 7;
struct mint {
int v;
mint(i64 x = 0) : v(x % P) {x < 0 ? x += P : 0;}
int val() const {return v;}
mint operator-() const {return -v;}
mint &operator+=(const mint &b) {
v += b.v - P, v += v >> 31 & P;
return *this;
}
mint &operator-=(const mint &b) {
v -= b.v, v += v >> 31 & P;
return *this;
}
mint &operator*=(const mint &b) {
v = i64(v) * b.v % P;
return *this;
}
mint &operator/=(const mint &b) {return *this *= b.inv();}
mint pow(int n) const {
mint c = 1, a = *this;
for (; n; a *= a, n /= 2) if (n % 2) c *= a;
return c;
}
mint inv() const {return this->pow(P - 2);}
friend mint operator+(mint a, const mint &b) {return a += b;}
friend mint operator-(mint a, const mint &b) {return a -= b;}
friend mint operator*(mint a, const mint &b) {return a *= b;}
friend mint operator/(mint a, const mint &b) {return a /= b;}
friend ostream &operator<<(ostream &os, const mint &a) {
return os << a.val();
}
};
constexpr int N = 2e5 + 5;
mint sum1[4 * N], sum2[4 * N], tag1[4 * N], tag2[4 * N];
#define ls (2 * i)
#define rs (2 * i + 1)
void upd(int i) {
sum1[i] = sum1[ls] + sum1[rs];
sum2[i] = sum2[ls] + sum2[rs];
}
void push1(int i, mint v) {
sum1[i] *= v;
tag1[i] *= v;
}
void push2(int i, mint v) {
sum2[i] *= v;
tag2[i] *= v;
}
void down(int i) {
if (tag1[i].val() != 1) {
push1(ls, tag1[i]);
push1(rs, tag1[i]);
tag1[i] = 1;
}
if (tag2[i].val() != 1) {
push2(ls, tag2[i]);
push2(rs, tag2[i]);
tag2[i] = 1;
}
}
void build(int i, int l, int r) {
tag1[i] = tag2[i] = 1;
sum1[i] = sum2[i] = 0;
if (l == r) {
return;
}
int mid = (l + r) / 2;
build(ls, l, mid);
build(rs, mid + 1, r);
upd(i);
}
void modify(int i, int l, int r, int x, mint v1, mint v2) {
if (l == r) {
sum1[i] = v1;
sum2[i] = v2;
return;
}
down(i);
int mid = (l + r) / 2;
if (x <= mid)
modify(ls, l, mid, x, v1, v2);
else
modify(rs, mid + 1, r, x, v1, v2);
upd(i);
}
void range(int i, int l, int r, int ql, int qr, mint v1, mint v2) {
if (ql > r || qr < l) return;
if (ql <= l && qr >= r) return push1(i, v1), push2(i, v2);
down(i);
int mid = (l + r) / 2;
range(ls, l, mid, ql, qr, v1, v2);
range(rs, mid + 1, r, ql, qr, v1, v2);
upd(i);
}
mint query1(int i, int l, int r, int ql, int qr) {
if (ql > r || qr < l) return 0;
if (ql <= l && qr >= r) return sum1[i];
down(i);
int mid = (l + r) / 2;
mint res = 0;
if (ql <= mid)
res += query1(ls, l, mid, ql, qr);
if (qr > mid)
res += query1(rs, mid + 1, r, ql, qr);
return res;
}
mint query2(int i, int l, int r, int ql, int qr) {
if (ql > r || qr < l) return 0;
if (ql <= l && qr >= r) return sum2[i];
down(i);
int mid = (l + r) / 2;
mint res = 0;
if (ql <= mid)
res += query2(ls, l, mid, ql, qr);
if (qr > mid)
res += query2(rs, mid + 1, r, ql, qr);
return res;
}
struct BIT {
int n;
vector<int> a;
BIT(int n = 0) : n(n), a(n + 1) {}
void modify(int x, int v) {
for (int i = x + 1; i <= n; i += i & -i) {
a[i] += v;
}
}
int query(int x) {
int res = 0;
for (int i = x + 1; i > 0; i -= i & -i) {
res += a[i];
}
return res;
}
};
int main() {
cin.tie(0)->sync_with_stdio(0);
int n;
cin >> n;
vector<int> a(n), b(n);
for (int i = 0; i < n; i++) {
int x, y;
cin >> x >> y;
--x, --y;
a[x] = y;
b[x] = n - y - 1;
}
vector<mint> pw2(n + 1);
pw2[0] = 1;
for (int i = 1; i <= n; i++) {
pw2[i] = pw2[i - 1] * 2;
}
mint iv2 = mint(2).inv();
mint ans = 0;
for (int i = 0; i < n - 1; i++) {
ans += pw2[i] * (pw2[n - i - 1] - 1) * 4;
}
auto solve = [&](auto a) {
build(1, 0, n - 1);
BIT A(n), B(n);
for (int i = 0; i < n; i++) {
B.modify(a[i], 1);
}
mint res = 0;
for (int i = 0; i < n - 1; i++) {
B.modify(a[i], -1);
range(1, 0, n - 1, 0, a[i] - 1, iv2, 1);
modify(1, 0, n - 1, a[i], pw2[A.query(a[i]) + n - i - 1 - B.query(a[i])],
pw2[A.query(a[i])]);
res += query1(1, 0, n - 1, a[i], n - 1);
res -= query2(1, 0, n - 1, a[i], n - 1);
A.modify(a[i], 1);
range(1, 0, n - 1, a[i] + 1, n - 1, 2, 2);
}
return res * 2;
};
ans -= solve(a) + solve(b);
cout << ans << "\n";
return 0;
}
詳細信息
Test #1:
score: 4.16667
Accepted
time: 0ms
memory: 16224kb
input:
2 1 2 2 1
output:
2
result:
ok single line: '2'
Test #2:
score: 4.16667
Accepted
time: 3ms
memory: 16208kb
input:
3 1 1 2 2 3 3
output:
10
result:
ok single line: '10'
Test #3:
score: 4.16667
Accepted
time: 0ms
memory: 16280kb
input:
3 1 1 2 3 3 2
output:
12
result:
ok single line: '12'
Test #4:
score: 4.16667
Accepted
time: 3ms
memory: 16224kb
input:
40 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40
output:
441563023
result:
ok single line: '441563023'
Test #5:
score: 4.16667
Accepted
time: 0ms
memory: 15972kb
input:
10 10 8 9 3 5 6 3 4 6 10 4 2 2 1 1 5 7 7 8 9
output:
13884
result:
ok single line: '13884'
Test #6:
score: 4.16667
Accepted
time: 0ms
memory: 15980kb
input:
200 84 134 66 9 126 191 158 17 61 172 92 170 153 21 52 65 8 169 74 124 113 168 151 179 63 100 104 115 156 63 134 24 91 51 179 66 45 85 155 58 48 59 187 50 49 68 64 97 105 148 51 78 41 18 39 32 60 26 144 92 190 57 89 189 78 113 57 74 130 6 37 127 161 95 27 72 17 86 15 150 25 55 93 144 35 41 40 177 16...
output:
685742506
result:
ok single line: '685742506'
Test #7:
score: 4.16667
Accepted
time: 0ms
memory: 16108kb
input:
200 52 196 46 26 28 85 110 147 98 76 7 11 61 162 65 172 155 173 11 99 20 128 160 96 4 41 93 97 175 69 56 112 113 159 137 15 48 177 151 114 78 9 108 61 12 197 85 174 106 180 95 47 141 55 10 160 138 101 39 16 168 142 122 140 198 118 188 199 41 182 158 165 1 30 112 44 180 120 103 71 8 12 36 164 84 32 3...
output:
124475018
result:
ok single line: '124475018'
Test #8:
score: 4.16667
Accepted
time: 0ms
memory: 15932kb
input:
200 136 89 137 132 38 180 86 54 135 58 154 86 60 143 175 43 31 154 196 94 174 62 75 61 148 40 78 5 59 106 200 95 151 187 157 34 80 198 18 139 121 26 113 175 41 162 188 19 97 129 168 1 125 27 64 3 197 15 124 155 142 14 143 29 53 150 50 6 109 164 63 13 25 120 127 144 102 9 73 100 191 46 69 39 66 181 1...
output:
715335688
result:
ok single line: '715335688'
Test #9:
score: 4.16667
Accepted
time: 0ms
memory: 16228kb
input:
200 36 64 102 134 124 79 34 84 61 198 189 11 65 61 87 199 24 108 93 55 177 91 27 13 158 35 25 53 125 39 94 59 195 194 99 197 57 6 187 70 180 180 77 112 83 9 191 69 197 116 153 131 132 10 47 90 45 103 107 73 100 178 1 105 129 173 89 17 155 175 33 156 70 196 5 37 75 58 43 115 140 143 64 3 114 153 131 ...
output:
352110458
result:
ok single line: '352110458'
Test #10:
score: 4.16667
Accepted
time: 8ms
memory: 16184kb
input:
3000 832 929 2510 1612 1066 1193 2648 415 1675 47 1291 1049 800 541 2704 1698 1952 2162 2967 1033 2045 246 208 1291 320 2902 2195 1501 671 2609 585 87 233 615 2015 353 2315 831 102 2439 1482 234 2718 2920 1344 2121 2081 2851 596 1215 2724 2686 2664 1120 759 1710 1142 1419 723 688 1918 314 1436 305 1...
output:
367742471
result:
ok single line: '367742471'
Test #11:
score: 4.16667
Accepted
time: 7ms
memory: 16072kb
input:
3000 2565 2285 1204 648 399 1416 2642 2974 377 578 2430 2120 2479 1986 1741 891 1279 1714 1458 2778 726 283 233 349 366 2443 216 504 2631 1320 2367 1809 1981 1611 2757 2039 1176 1965 2258 1032 841 2653 1356 772 401 613 1452 2181 2781 997 1726 112 1988 2217 468 1253 2247 2703 1785 65 170 1724 2189 13...
output:
361767698
result:
ok single line: '361767698'
Test #12:
score: 4.16667
Accepted
time: 3ms
memory: 16164kb
input:
3000 2161 2305 62 449 2255 33 562 2460 1361 624 303 406 2593 2412 2085 1435 829 1360 579 104 1480 2512 444 2215 1898 2213 787 1186 1929 2672 126 1524 78 1517 390 469 1517 1725 2322 2370 2523 1244 89 2662 2027 405 1434 2223 738 350 2769 2422 1599 635 2969 1726 2665 920 2807 984 997 1843 2501 1268 551...
output:
939648717
result:
ok single line: '939648717'
Test #13:
score: 4.16667
Accepted
time: 11ms
memory: 16092kb
input:
3000 2928 2045 465 2436 1689 1544 1604 3000 1458 1857 2016 626 845 1499 1456 1355 1436 1016 2805 139 1358 728 1191 2714 2315 2319 1137 1683 437 1488 2941 2378 1950 2791 735 2390 503 870 502 815 2474 2060 1162 563 2859 2231 2256 1665 2348 1779 2822 2040 59 1702 1179 1147 213 1186 1316 465 378 2669 24...
output:
735767830
result:
ok single line: '735767830'
Test #14:
score: 4.16667
Accepted
time: 737ms
memory: 20944kb
input:
200000 122662 151255 103133 95790 180493 53172 9515 79871 147095 98989 4621 166303 37406 39509 124810 164228 150748 120240 38634 42188 189408 6049 104316 5904 191264 33124 146064 91624 176995 79336 101702 62000 154591 153939 107190 70247 127902 87486 83534 143667 74255 73859 16583 156262 48534 87288...
output:
898907686
result:
ok single line: '898907686'
Test #15:
score: 4.16667
Accepted
time: 730ms
memory: 20952kb
input:
200000 1146 147943 74015 23202 37200 11716 12231 15669 160789 98861 79922 101600 160900 120625 140815 39108 5321 174086 55377 169968 152125 125950 137868 30575 176918 123585 39296 26163 43128 189612 75277 167118 151497 79836 196319 43878 9830 158793 86203 91213 55262 132113 98062 170947 135203 2739 ...
output:
914111351
result:
ok single line: '914111351'
Test #16:
score: 4.16667
Accepted
time: 729ms
memory: 20976kb
input:
200000 137951 80053 147068 20166 164904 77176 18377 187810 192399 106481 162948 101924 168490 121992 50218 97379 4648 114702 178245 52054 40266 191996 192950 167106 172544 89078 107630 116988 91768 187115 147885 37036 140488 58351 115378 3733 35043 165422 24344 172409 135603 137020 36387 72344 16552...
output:
54875572
result:
ok single line: '54875572'
Test #17:
score: 4.16667
Accepted
time: 736ms
memory: 21016kb
input:
200000 125113 52151 54399 174325 39847 5176 113324 34790 112043 80241 194906 8219 46210 62674 185079 2835 27848 36235 86621 62528 91586 105774 108662 63539 53689 144231 55083 133043 161912 160517 103554 127720 127355 82884 69668 42070 194247 59228 59728 62428 77041 60814 147535 151829 83348 49415 10...
output:
331321172
result:
ok single line: '331321172'
Test #18:
score: 4.16667
Accepted
time: 735ms
memory: 21032kb
input:
200000 148467 196196 59570 32569 43300 150163 106864 179506 44710 7861 126489 36985 92869 145559 168075 165597 172944 58211 185218 45265 36865 22477 186259 47809 78929 2972 110776 179836 148188 50052 148475 58250 139536 130593 187465 74312 52245 20919 186648 103807 106676 64317 158302 194808 139205 ...
output:
670903486
result:
ok single line: '670903486'
Test #19:
score: 4.16667
Accepted
time: 722ms
memory: 21064kb
input:
200000 118741 54416 84673 50583 125527 183457 130955 41355 198451 76091 192867 83025 12417 60836 154143 106845 101775 120711 45632 137011 82236 120081 198882 115811 156188 79451 139426 77863 192853 154944 76099 162600 131447 140971 167796 65644 94884 173270 118910 31036 48555 77151 191962 100708 583...
output:
119277856
result:
ok single line: '119277856'
Test #20:
score: 4.16667
Accepted
time: 750ms
memory: 21084kb
input:
200000 25919 157577 52070 70492 195283 116530 175162 164800 29155 161488 176976 198528 102128 83574 5288 60871 50962 148508 165131 99401 125921 85685 148954 19353 1085 170658 45509 28394 110635 38519 93813 17635 1475 4010 197217 51842 71242 92482 14412 114969 140038 104806 81324 1004 122327 97085 15...
output:
829665267
result:
ok single line: '829665267'
Test #21:
score: 4.16667
Accepted
time: 735ms
memory: 21036kb
input:
200000 75381 95442 165757 39926 184535 199357 62897 169864 42131 142836 139478 115804 73259 121470 165633 58667 111377 37780 61191 164856 48275 94705 25206 162359 167467 150105 133325 35521 174337 119358 85387 162752 80533 111330 35880 65641 96827 110772 397 173072 160588 146464 95327 127468 26880 1...
output:
848909429
result:
ok single line: '848909429'
Test #22:
score: 4.16667
Accepted
time: 743ms
memory: 20944kb
input:
200000 132243 100677 92043 100356 188112 51073 152558 116222 146748 178446 4378 60443 168127 176721 69076 92867 81021 15818 33787 129636 57659 160605 52712 133268 174787 135558 143651 174978 120676 65798 101205 108692 106440 181849 62480 103905 153521 2883 41660 98221 42815 146506 165087 157506 5558...
output:
594822678
result:
ok single line: '594822678'
Test #23:
score: 4.16667
Accepted
time: 762ms
memory: 21032kb
input:
200000 79098 172025 134166 21235 58752 142815 78518 63731 188415 40546 7103 143530 5780 180152 49437 49445 118976 189488 95550 103211 176397 16343 67324 30208 107410 92784 77505 79291 187274 72920 190660 154019 191188 64617 23953 75819 170442 166410 29898 55679 119219 199132 93672 145757 186262 1309...
output:
234191289
result:
ok single line: '234191289'
Test #24:
score: 4.16667
Accepted
time: 757ms
memory: 20952kb
input:
200000 127786 114030 144165 62637 178979 85987 96380 70256 182902 66628 40935 181139 44722 2343 166659 45855 160742 183280 19615 196111 196435 51114 6818 28159 103140 51046 90067 25785 154749 87466 183012 97279 54027 180418 154772 104911 74600 118662 157754 86479 109510 148811 65081 194022 114722 10...
output:
364003520
result:
ok single line: '364003520'