QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#462491#8535. Mooball Teams IIIzlxFTH100 ✓762ms21084kbC++144.5kb2024-07-03 20:16:242024-07-03 20:16:26

Judging History

你现在查看的是最新测评结果

  • [2024-07-03 20:16:26]
  • 评测
  • 测评结果:100
  • 用时:762ms
  • 内存:21084kb
  • [2024-07-03 20:16:24]
  • 提交

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'