QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #941595 | #4055. 整数序列 | zlt | 0 | 0ms | 0kb | C++14 | 4.3kb | 2025-03-18 16:19:01 | 2025-03-18 16:19:14 |
Judging History
answer
// Problem: P8349 [SDOI/SXOI2022] 整数序列
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P8349
// Memory Limit: 512 MB
// Time Limit: 7000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;
namespace IO {
const int maxn = 1 << 20;
char ibuf[maxn], *iS, *iT, obuf[maxn], *oS = obuf;
inline char gc() {
return (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, maxn, stdin), (iS == iT ? EOF : *iS++) : *iS++);
}
template<typename T = int>
inline T read() {
char c = gc();
T x = 0;
bool f = 0;
while (c < '0' || c > '9') {
f |= (c == '-');
c = gc();
}
while (c >= '0' && c <= '9') {
x = (x << 1) + (x << 3) + (c ^ 48);
c = gc();
}
return f ? ~(x - 1) : x;
}
inline void flush() {
fwrite(obuf, 1, oS - obuf, stdout);
oS = obuf;
}
struct Flusher {
~Flusher() {
flush();
}
} AutoFlush;
inline void pc(char ch) {
if (oS == obuf + maxn) {
flush();
}
*oS++ = ch;
}
template<typename T>
inline void write(T x) {
static char stk[64], *tp = stk;
if (x < 0) {
x = ~(x - 1);
pc('-');
}
do {
*tp++ = x % 10;
x /= 10;
} while (x);
while (tp != stk) {
pc((*--tp) | 48);
}
}
template<typename T>
inline void writesp(T x) {
write(x);
pc(' ');
}
template<typename T>
inline void writeln(T x) {
write(x);
pc('\n');
}
}
using IO::read;
using IO::write;
using IO::pc;
using IO::writesp;
using IO::writeln;
const int maxn = 300100;
int n, m, a[maxn], b[maxn], g[maxn], d[maxn];
ll f[maxn << 1];
vector<int> ap[maxn];
struct node {
int l, r, o;
node(int a = 0, int b = 0, int c = 0) : l(a), r(b), o(c) {}
} c[maxn];
int pre[maxn], suf[maxn];
void solve() {
n = read();
m = read();
for (int i = 1; i <= n; ++i) {
a[i] = read();
ap[a[i]].pb(i);
}
for (int i = 1; i <= n; ++i) {
b[i] = read();
}
map<pii, ll> mp;
mems(f, 0x3f);
while (m--) {
int x = read();
int y = read();
if (ap[x].size() > ap[y].size() || (ap[x].size() == ap[y].size() && x > y)) {
swap(x, y);
}
if (mp.find(mkp(x, y)) != mp.end()) {
writeln(mp[mkp(x, y)]);
continue;
}
int tot = 0;
for (int i = 0; i < (int)ap[x].size(); ++i) {
d[i] = lower_bound(ap[y].begin(), ap[y].end(), ap[x][i]) - ap[y].begin();
}
c[++tot] = node(0, d[0] - 1, 0);
for (int i = 0; i + 1 < (int)ap[x].size(); ++i) {
c[++tot] = node(i, i, 1);
c[++tot] = node(d[i], d[i + 1] - 1, 0);
}
c[++tot] = node((int)ap[x].size() - 1, (int)ap[x].size() - 1, 1);
c[++tot] = node(d[(int)ap[x].size() - 1], (int)ap[y].size() - 1, 0);
int s = 0;
for (int i = 1; i <= tot; ++i) {
pre[i] = min(pre[i - 1], s);
s += (c[i].o ? c[i].r - c[i].l + 1 : -(c[i].r - c[i].l + 1));
pre[i] = min(pre[i], s);
}
suf[tot + 1] = s;
for (int i = tot; i; --i) {
suf[i] = max(suf[i + 1], s);
s -= (c[i].o ? c[i].r - c[i].l + 1 : -(c[i].r - c[i].l + 1));
suf[i] = max(suf[i], s);
}
int tt = 0;
for (int i = 1; i <= tot; ++i) {
if (c[i].o) {
for (int j = c[i].l; j <= c[i].r; ++j) {
g[++tt] = ap[x][j];
++s;
}
continue;
}
int p = pre[i - 1], q = suf[i + 1];
if (q >= p - 2) {
for (int j = c[i].l; j <= c[i].r; ++j) {
g[++tt] = ap[y][j];
}
continue;
}
int t = s, z = c[i].l;
while (t >= p) {
g[++tt] = ap[y][z++];
--t;
}
s -= (c[i].r - c[i].l + 1);
t = s;
z = c[i].r;
int r = tt;
while (t <= q) {
g[++tt] = ap[y][z--];
++t;
}
reverse(g + r + 1, g + tt + 1);
}
ll ans = -9e18, t = 0;
s = 0;
f[n] = 0;
for (int i = 1; i <= tt; ++i) {
s += (a[g[i]] == x ? 1 : -1);
t += b[g[i]];
ans = max(ans, t - f[s + n]);
f[s + n] = min(f[s + n], t);
}
writeln(mp[mkp(x, y)] = ans);
f[n] = 4e18;
s = 0;
for (int i = 1; i <= tt; ++i) {
s += (a[g[i]] == x ? 1 : -1);
f[s + n] = 4e18;
}
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 0
Runtime Error
input:
5000 4999 1242 1550 3974 121 3049 2220 2031 3596 4083 346 2893 1242 2610 4935 4633 4195 4937 3783 1241 1867 4633 3519 660 4861 3616 1628 4633 3519 137 2347 4634 1242 1469 781 1632 1051 3147 288 3154 4633 1993 288 780 1242 4086 4312 4924 328 137 3154 2738 756 1952 98 1524 3974 3072 3519 3346 1242 165...
output:
result:
Test #2:
score: 0
Runtime Error
input:
4999 5000 3440 4463 103 3377 2009 1045 2434 2920 2434 1564 2870 2732 749 1324 1178 4353 2127 1161 2482 853 1835 1830 3673 294 4750 4809 676 676 1374 1324 4039 2870 3962 788 4839 3204 1324 3440 3220 703 3440 391 2870 221 3440 4655 1461 2097 2612 4253 1865 2275 4011 3395 2612 829 1559 4216 2434 2434 1...
output:
result:
Test #3:
score: 0
Runtime Error
input:
5000 4999 721 2854 978 3366 2366 2071 3792 3235 3235 4826 3204 2352 2296 3204 2038 3159 3204 507 2366 1665 2338 2504 2247 3342 4826 4826 3456 1200 3204 2366 447 4608 1300 447 109 1933 162 3226 3258 74 3215 2951 2410 2262 721 4826 2808 1157 1180 1316 2421 481 3230 1316 3056 2359 322 3204 2262 3204 59...
output:
result:
Test #4:
score: 0
Runtime Error
input:
4999 5000 1169 743 965 2404 2438 551 4692 337 743 1866 2453 743 1866 1157 3204 2181 1311 4867 3139 56 955 4635 3301 2569 1067 700 1866 1165 4224 743 3620 2360 689 4746 1177 1157 2569 4357 4765 1043 2601 1169 1866 4044 4224 4727 743 743 3191 700 1675 1866 551 3301 4224 4217 2204 3735 1871 689 743 700...
output:
result:
Test #5:
score: 0
Runtime Error
input:
300000 1000000 210616 109093 194161 18266 74476 222692 179435 112558 155417 194161 60442 219569 121583 64920 210616 119012 79775 84215 18266 109093 18266 197546 74044 194161 162053 233329 119012 74476 8047 126329 194161 201328 189361 194161 112200 99319 74044 201328 289127 119012 179435 283375 19512...
output:
result:
Test #6:
score: 0
Runtime Error
input:
299999 1000000 215543 183462 57241 150146 75108 2589 28359 104656 85936 49139 272845 26114 183462 92642 110658 2589 218311 231610 144686 2589 161638 92555 130256 91926 28344 272662 51005 105130 131618 89779 28359 28420 172552 218311 92555 131618 144364 188255 2589 215543 57241 110658 25236 28344 131...
output:
result:
Test #7:
score: 0
Runtime Error
input:
150000 500000 132436 8515 14753 132436 44442 132436 63224 132436 132436 132436 10776 132436 132436 132436 106000 132436 132436 138973 18627 139106 106971 132436 132436 126363 135723 319 76472 10220 132436 132436 132436 132436 63083 48327 132436 81505 132436 132436 148574 132436 132436 132436 132436 ...
output:
1068142142 1655225246 530261633 1125887539 1315380311 1337243549 610772435 855266778 1857990366 992821984 995555499 521203661 1324305675 1218395792 1595023708 897045138 868747680 966790047 1125459045 1075768980 1697552843 1072385442 1172448570 824034058 1877789598 930008455 993214893 1153351012 1254...
result:
Test #8:
score: 0
Runtime Error
input:
150000 500000 5202 5202 5202 36166 5202 5202 95724 5202 5202 92605 5202 5202 5202 5202 64052 5202 5202 51686 5202 94344 147952 134686 124500 5202 5202 5202 5202 5202 5202 5202 5202 19171 5202 107149 5202 10457 92605 10677 5202 5202 5202 90631 5202 5202 5202 5202 5202 5202 5202 97189 64052 16557 5202...
output:
1282956208 1203392879 1680347551 997677571 1377920509 1516225244 1473045154 1085598608 1115976311 1189267746 1673860056 1103464182 1794803263 1166468498 1520532888 1635882851 504249763 1561528057 1760976523 589795308 798753505 1597116188 672593941 658927711 1682713789 1177387154 1054444159 155643411...
result:
Test #9:
score: 0
Runtime Error
input:
149999 500000 130539 130539 130539 135015 130539 68088 130539 135629 130539 130539 130539 130539 130539 129686 145610 73567 52505 130539 130539 130539 14931 38544 107261 130539 130539 51142 14931 68088 130539 35668 130539 130539 106082 61754 130539 65537 130539 130539 69769 130539 130539 20244 10074...
output:
result:
Test #10:
score: 0
Runtime Error
input:
200000 500000 18780 73334 73334 129506 73334 28788 73334 73334 73334 73334 26535 36488 73334 73334 73334 121456 129506 119075 190638 142411 111475 73334 73334 91293 73334 73334 73334 73334 73334 73334 184692 178784 118264 129506 116620 118404 122852 36488 73334 163977 73334 50087 10210 199390 73334 ...
output:
result:
Test #11:
score: 0
Runtime Error
input:
200000 500000 117561 117561 108780 140071 76023 163608 147648 117561 117561 117561 117561 117561 146331 117561 117561 50485 117561 117561 117561 147648 169614 117561 117561 117561 117561 117561 134029 161477 117561 117561 74827 99188 117561 117561 117561 117561 186557 117561 117561 159944 50485 1244...
output:
result:
Test #12:
score: 0
Runtime Error
input:
300000 1000000 56219 143695 226286 249694 160309 135267 279081 101944 14091 99207 27252 286872 97823 160309 153937 193629 195292 241817 48132 241817 191469 52905 239169 295659 88239 133799 133799 8234 50907 228407 95709 268342 241817 296967 135267 116559 100835 104182 39121 71692 191469 133799 24181...
output:
result:
Test #13:
score: 0
Runtime Error
input:
300000 1000000 252427 92158 13474 286432 38970 155012 77876 141812 211941 90991 298722 187008 281303 130407 151235 239285 180713 183820 178795 151235 151161 286432 13474 126097 182453 225946 224795 126021 140814 123569 212222 183820 151235 248332 134648 27062 100877 3515 276112 138511 212687 13474 4...
output:
result:
Test #14:
score: 0
Runtime Error
input:
299999 1000000 102271 20892 168471 178536 165808 72575 225025 79470 180501 268666 197798 145975 243581 255187 142045 197006 30081 242593 83648 170294 86352 78447 177452 275062 165294 113565 142413 293611 280979 4033 272066 195915 122234 86343 79470 261560 26913 221328 168471 78447 18922 296613 10213...
output:
result:
Test #15:
score: 0
Runtime Error
input:
299999 1000000 151289 14535 244254 290111 288090 130841 27455 106184 47286 236908 173179 159601 134454 134838 14535 203110 92926 274608 87246 215015 245740 295574 123490 290111 134838 216821 114378 188238 134454 188365 234630 2226 97676 134838 290111 2226 44319 241093 115893 134838 43192 179884 1385...
output:
result:
Test #16:
score: 0
Runtime Error
input:
300000 1000000 147825 195767 150390 77132 239532 278774 160659 276921 115387 7629 183295 110547 290985 115387 91975 103610 40841 207522 145488 91975 111180 16525 178046 16950 295408 243529 247392 267715 278774 217808 16525 115387 194968 91975 77824 139035 253468 295408 32471 153777 237234 104953 147...
output:
result:
Test #17:
score: 0
Runtime Error
input:
300000 1000000 92527 298213 72198 196854 158708 76270 195790 236817 208173 208173 71266 17759 29102 195790 247368 262696 97153 164699 97153 106281 257441 210052 195790 111950 239957 179014 150594 241963 112387 273448 151221 150594 208173 136209 129633 46494 46494 84383 72786 162998 46494 46494 17291...
output:
result:
Test #18:
score: 0
Runtime Error
input:
299999 1000000 174942 205062 214513 219196 259901 19736 239253 95131 119460 179415 8195 48699 123674 252242 179415 204410 61013 276817 145744 121754 204410 182272 255628 274322 137057 82468 231315 122482 222185 63411 123674 186416 161540 77373 206186 23868 112918 123674 95131 236420 204496 178859 11...
output:
result:
Test #19:
score: 0
Runtime Error
input:
300000 1000000 229819 100462 229819 78236 229819 249816 70315 167375 157866 183526 100462 116410 105610 50013 71906 100462 1512 168934 147968 58495 52997 92028 291180 30449 218217 299205 90916 100462 69006 290092 36728 261594 1512 142526 228482 1512 272954 1512 142691 123023 1512 47880 50013 76498 1...
output:
result:
Test #20:
score: 0
Runtime Error
input:
300000 1000000 135822 88561 243121 279557 10947 146084 66559 172695 40359 288955 234013 187141 288955 187141 271817 84283 208724 139740 288955 266331 15885 59084 225069 124976 187141 103698 288955 187141 92132 238696 291003 23394 40340 109700 88561 86940 51845 266331 255230 288955 229039 239891 1871...