QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#611752 | #7031. Supreme Command | ucup-team4906# | WA | 323ms | 39068kb | C++20 | 6.0kb | 2024-10-04 22:31:19 | 2024-10-04 22:31:22 |
Judging History
answer
#include<bits/stdc++.h>
#define F(i, a, b) for(int i = a; i <= b; i ++)
#define pii pair<int, int>
#define fi first
#define se second
#define int long long
using namespace std;
const int N = 3e5 + 10;
int n, m, is_q[N];
pii a[N];
pii res[N];
int ans[N], Y[N];
typedef array<int, 3> a3;
int f1[N], f2[N];
vector<a3> op1[N], op2[N];
int lowbit(int x) {return x & -x;}
void add1(int x, int d) {for(; x <= n; x += lowbit(x)) f1[x] += d;}
int cal1(int l, int r) {
if(l > r) return 0;
int res = 0; l --;
for(; r; r -= lowbit(r)) res += f1[r];
for(; l; l -= lowbit(l)) res -= f1[l];
return res;
}
void add2(int x, int d) {for(; x <= n; x += lowbit(x)) f2[x] += d;}
int cal2(int l, int r) {
if(l > r) return 0;
int res = 0; l --;
for(; r; r -= lowbit(r)) res += f2[r];
for(; l; l -= lowbit(l)) res -= f2[l];
return res;
}
void sol() {
cin >> n >> m;
F(i, 1, n) {
int x, y; cin >> x >> y;
a[i] = {x, y};
Y[x] = y;
}
F(i, 1, m) ans[i] = 0, is_q[i] = 0;
F(i, 1, n) op1[i].clear(), op2[i].clear(), f1[i] = f2[i] = 0;
if(n == 1) {
F(i, 1, m) {
char op; cin >> op;
if(op == '!') cout << "0\n";
else if(op == '?') {
int x; cin >> x;
cout << 1 << " " << 1 << "\n";
}
}
return;
}
int x1 = 1, y1 = 1, x2 = n, y2 = n, fx1 = 1, fx2 = n, fy1 = 1, fy2 = n;
int f1 = 0, f2 = 0;
// x1: 包含了哪些位置 fx1: 目前的实际位置
// f1 是否合并上下的 只保留fx1
int tot1 = 0, tot2 = 0;
F(i, 1, m) {
char op; cin >> op;
if(op == '!') {
is_q[i] = 0;
if(f1 && f2) ans[i] = n * (n - 1) / 2;
else if(f1) {
int tmp1 = y1, tmp2 = n - y2 + 1;
ans[i] = tmp1 * (tmp1 - 1) / 2 + tmp2 * (tmp2 - 1) / 2;
} else if(f2) {
int tmp1 = x1, tmp2 = n - x2 + 1;
ans[i] = tmp1 * (tmp1 - 1) / 2 + tmp2 * (tmp2 - 1) / 2;
} else {
// op1 表示小于等于这个x的限制
op1[x1].push_back({y1, 0, i});
op1[x1].push_back({y2, 1, i});
op2[x2].push_back({y1, 0, i});
op2[x2].push_back({y2, 1, i});
}
} else if(op == '?') {
is_q[i] = 2;
int p; cin >> p;
auto [x, y] = a[p];
if(f1) x = fx1;
else if(x <= x1) x = fx1;
else if(x >= x2) x = fx2;
else x -= tot1;
if(f2) y = fy1;
else if(y <= y1) y = fy1;
else if(y >= y2) y = fy2;
else y -= tot2;
res[i] = {x, y};
} else {
is_q[i] = 1;
int x; cin >> x;
if(op == 'U') {
tot1 += x;
if(f1) { // 当前已经合并了
fx1 = max(1ll, fx1 - x);
continue;
}
// 挪到1的位置
int nd = min(fx1 - 1, x);
x -= nd;
fx1 -= nd, fx2 -= nd;
while(x) {
x1 ++, fx2 --;
if(x1 == x2) {
assert(fx2 == 1);
f1 = 1;
break;
}
x --;
}
} else if(op == 'D') {
tot1 -= x;
if(f1) {
fx1 = min(n, fx1 + x);
continue;
}
int nd = min(n - fx2, x);
x -= nd;
fx1 += nd, fx2 += nd;
while(x) {
x2 --, fx1 ++;
if(x1 == x2) {
assert(fx1 == n);
assert(fx1 == fx2);
f1 = 1;
break;
}
x --;
}
} else if(op == 'L') {
tot2 += x;
if(f2) {
fy1 = max(1ll, fy1 - x);
continue;
}
int nd = min(fy1 - 1, x);
x -= nd;
fy1 -= nd, fy2 -= nd;
while(x) {
y1 ++, fy2 --;
if(y1 == y2) {
assert(fy2 == 1);
f2 = 1;
break;
}
x --;
}
} else {
tot2 -= x;
if(f2) {
fy1 = min(n, fy1 + x);
continue;
}
int nd = min(n - fy2, x);
x -= nd;
fy1 += nd, fy2 += nd;
while(x) {
y2 --, fy1 ++;
if(y1 == y2) {
assert(fy1 == n);
assert(fy1 == fy2);
f2 = 1;
break;
}
x --;
}
}
}
}
F(x, 1, n) {
add1(Y[x], 1);
for(auto [y, flag, id] : op1[x]) {
int sum = 0;
if(flag == 0) sum = cal1(1, y);
else sum = cal1(y, n);
ans[id] += 1ll * sum * (sum - 1) / 2;
}
}
for(int x = n; x >= 1; x --) {
add2(Y[x], 1);
for(auto [y, flag, id] : op2[x]) {
int sum = 0;
if(flag == 0) sum = cal2(1, y);
else sum = cal2(y, n);
ans[id] += 1ll * sum * (sum - 1) / 2;
}
}
F(i, 1, m) {
if(is_q[i] == 2) cout << res[i].fi << " " << res[i].se << "\n";
if(is_q[i] == 0) cout << ans[i] << "\n";
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t; cin >> t;
F(i, 1, t) sol();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 17980kb
input:
1 4 9 3 4 2 1 4 2 1 3 L 2 ? 1 ? 2 R 1 ? 1 ? 3 ! U 3 !
output:
3 2 2 1 3 3 4 2 0 3
result:
ok 6 lines
Test #2:
score: 0
Accepted
time: 185ms
memory: 24492kb
input:
500 2000 2000 492 502 1394 1025 980 1484 1135 599 760 242 575 1393 833 341 1364 453 1692 1515 1303 7 1429 1519 887 86 205 1874 1483 1797 649 1677 1717 298 416 1673 1696 896 1998 1154 638 1725 667 96 1467 1788 1438 759 285 1987 1985 736 95 140 596 1076 1089 238 1212 247 1287 1705 891 1237 941 622 930...
output:
170 1229 0 1610 1081 0 616 1509 0 1419 1109 0 1584 1103 0 459 1193 0 1891 1713 0 806 187 0 115 81 0 1035 378 0 1673 276 0 529 1976 0 1380 639 0 397 1375 0 144 806 0 579 495 0 1817 1065 0 369 828 0 1226 790 0 740 1967 0 37 311 0 1466 391 0 160 898 0 97 1023 0 1086 754 0 670 1932 0 831 909 0 1964 255 ...
result:
ok 333000 lines
Test #3:
score: 0
Accepted
time: 305ms
memory: 39068kb
input:
4 300000 300000 80970 187487 294038 86632 10049 18427 97971 56733 248346 155658 75748 147098 271323 190205 76134 226265 76477 80456 256736 133100 161354 25074 238317 189162 95678 281762 40568 292572 1464 5702 173488 154848 218234 95786 258378 278765 145920 82902 4863 55628 114808 187456 83016 166159...
output:
287799 284434 0 176534 9959 0 206748 80053 0 132450 71141 0 182472 63837 0 50205 137287 0 28907 154017 0 92821 240433 0 261606 217699 0 145727 281330 0 56 189849 0 152538 296794 0 106827 98478 0 44987 46354 0 199410 263116 0 173533 3989 0 296407 251081 0 194428 130556 0 146819 198385 0 270813 257587...
result:
ok 333333 lines
Test #4:
score: 0
Accepted
time: 312ms
memory: 24996kb
input:
5 200000 200000 83663 150834 52609 106576 76810 195918 138933 98816 110278 145244 135053 163738 135741 194310 128700 127220 83979 109363 148309 53887 121241 91879 190186 75581 132110 176318 132515 198698 53610 67714 108291 88174 100902 97699 144230 45429 144942 154479 132992 48008 131132 117094 1602...
output:
14826 200000 191167 65452 42684 76298 30428 141566 57556 51844 5329 10040 170673 132526 171518 18233 86475 190065 80831 76686 52206 186080 146858 95514 10827 119585 126186 190237 161355 90093 48356 178130 47519 60570 83546 138415 116318 163592 54456 98656 179470 116306 191241 24049 58564 12160 10300...
result:
ok 500000 lines
Test #5:
score: 0
Accepted
time: 323ms
memory: 24760kb
input:
4 300000 300000 275361 116025 61510 272401 86493 295560 126844 206890 180147 56921 253572 8795 164582 69337 212996 93644 260724 57509 128125 51578 11967 220901 278650 143108 11700 164491 38662 144478 81044 71636 214854 288774 44122 298906 271792 143176 132572 20587 145020 270141 189966 242186 68114 ...
output:
226820 114090 244013 241137 73852 82413 235541 203730 140067 102292 172324 112718 119967 53358 111564 207031 159951 148360 164708 104351 285243 236856 283498 58083 128034 247272 274035 240873 202242 24095 67965 268962 5830 170844 265681 248323 200812 258093 191663 66872 210040 158080 271555 224195 1...
result:
ok 333333 lines
Test #6:
score: -100
Wrong Answer
time: 0ms
memory: 15860kb
input:
2 2 1 1 1 2 2 ! 1 14 1 1 ! ? 1 L 1 ? 1 ! U 1 ! ? 1 R 1 ? 1 ! D 1 ! ? 1
output:
0 0 1 1 1 1 0 0 1 1 1 1 0
result:
wrong answer 10th lines differ - expected: '0', found: ''