QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#8625 | #1060. 快速查询 | Qingyu | 100 ✓ | 219ms | 9860kb | C++20 | 3.4kb | 2021-04-03 10:54:37 | 2021-12-19 10:39:05 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
const int P = 1e7 + 19;
typedef long long ll;
template <typename T> void chkmax(T &x, T y)
{
x = max(x, y);
}
template <typename T> void chkmin(T &x, T y)
{
x = min(x, y);
}
template <typename T> void read(T &x)
{
x = 0;
int f = 1;
char c = getchar();
for (; !isdigit(c); c = getchar())
if (c == '-')
f = -f;
for (; isdigit(c); c = getchar())
x = x * 10 + c - '0';
x *= f;
}
int power(int x, int y)
{
if (y == 0)
return 1;
int tmp = power(x, y / 2);
if (y % 2 == 0)
return 1ll * tmp * tmp % P;
else
return 1ll * tmp * tmp % P * x % P;
}
void update(int &x, int y)
{
x += y;
if (x >= P)
x -= P;
}
map <int, int> mp;
int n, m, q, ans, sum, inv;
pair <int, int> a[MAXN];
pair <int, int> tag, all;
int type[MAXN], home[MAXN], val[MAXN];
void work(int timer, int type, int home, int val)
{
if (type == 1)
{
if (a[home].first < all.first)
update(sum, P - (1ll * all.second * tag.first + tag.second) % P);
else
update(sum, P - (1ll * a[home].second * tag.first + tag.second) % P);
a[home].first = timer;
a[home].second = 1ll * (val - tag.second + P) * inv % P;
update(sum, val);
}
if (type == 2)
{
update(tag.second, val);
update(sum, 1ll * n * val % P);
}
if (type == 3)
{
sum = 1ll * sum * val % P;
inv = 1ll * inv * home % P;
tag.first = 1ll * tag.first * val % P;
tag.second = 1ll * tag.second * val % P;
}
if (type == 4)
{
sum = 1ll * n * val % P;
all = make_pair(timer, val);
tag = make_pair(1, 0), inv = 1;
}
if (type == 5)
{
if (a[home].first < all.first)
update(ans, (1ll * all.second * tag.first + tag.second) % P);
else
update(ans, (1ll * a[home].second * tag.first + tag.second) % P);
}
if (type == 6)
{
update(ans, sum);
}
}
int main()
{
read(n), read(q);
for (int i = 1; i <= q; i++)
{
read(type[i]);
if (type[i] == 1)
{
read(home[i]), read(val[i]);
val[i] = (val[i] % P + P) % P;
}
else if (type[i] == 5)
read(home[i]);
else if (type[i] != 6)
{
read(val[i]);
val[i] = (val[i] % P + P) % P;
}
if (type[i] == 3)
{
if (val[i] == 0)
type[i] = 4;
else
home[i] = power(val[i], P - 2);
}
}
for (int i = 1; i <= q; i++)
{
if (type[i] == 1 || type[i] == 5)
{
if (mp.count(home[i]))
home[i] = mp[home[i]];
else
home[i] = mp[home[i]] = ++m;
}
}
int T;
read(T);
int timer = 1;
inv = 1;
tag = make_pair(1, 0);
while (T--)
{
int x, y;
read(x), read(y);
y %= q, x = (x + y) % q;
for (int i = 1; i <= q; i++, x = (x + y) >= q ? (x + y - q) : (x + y), timer++)
work(timer, type[x + 1], home[x + 1], val[x + 1]);
}
cout << ans << endl;
return 0;
}
詳細信息
Subtask #1:
score: 50
Accepted
Test #1:
score: 50
Accepted
time: 50ms
memory: 9304kb
input:
452026 95958 1 285703 217433997 1 11660 355946119 1 154677 958212086 1 45777 559001183 1 149425 708949937 1 199039 -627813211 1 421465 878181683 1 18566 -840518154 1 268546 -956473636 1 6627 -168874651 1 165349 796846652 1 389787 -241387034 2 856579071 2 776291767 1 361873 220652502 1 34945 3586417 5 367745 1 378171 -432131943 1 397272 -467145032 3 122665093 2 728212293 4 741318555 1 113302 68576484 1 216580 319789214 1 62106 -541415383 1 369237 83340100 1 399795 671764281 1 115658 -666814276 1 ...
output:
7032812
result:
ok single line: '7032812'
Test #2:
score: 0
Accepted
time: 35ms
memory: 8868kb
input:
483072 93455 3 127269075 1 302644 -819206705 1 324283 176567456 1 362914 -123696183 1 269012 35941289 1 320675 371602507 2 621029853 1 261791 42607160 1 134081 -311548238 1 39566 -639742963 1 148195 248115767 2 698644799 1 14757 -854683791 3 568083880 4 -307679829 1 81614 58671469 4 -123658687 1 263532 -369159133 1 71225 -352896939 1 394264 -407425476 1 214476 82084627 1 426845 -282517247 4 725604134 1 282596 -924017739 6 1 160255 -578908643 1 233183 -523051742 1 131750 829579993 3 151253278 4 3...
output:
4330039
result:
ok single line: '4330039'
Test #3:
score: 0
Accepted
time: 40ms
memory: 9428kb
input:
451320 98796 1 273886 584382657 1 72767 882120348 2 -500581825 1 371431 -890794733 1 388789 575894740 1 416938 55821666 4 -139712863 1 391097 644330384 2 -469419669 1 448782 107966848 1 235509 -986289 3 -858374275 1 123585 -837984190 2 929586510 6 1 401033 363310883 1 331019 468451209 1 96904 -127613335 5 95153 1 245039 621166244 1 140240 672911694 5 57507 3 155589866 1 308385 -734400663 1 276254 848592643 4 -302501114 1 236409 -672146656 1 240093 336282297 1 84873 -230917565 2 966646026 1 31166...
output:
2444116
result:
ok single line: '2444116'
Test #4:
score: 0
Accepted
time: 42ms
memory: 9492kb
input:
482366 98045 1 24349 377283548 1 453704 -854792539 6 1 237007 242624318 1 88252 393839755 6 1 228412 125093668 1 181999 240899085 4 -558162897 1 206599 674854997 1 277268 -501664106 4 -725152265 1 108652 -772913438 1 314782 64055034 1 188046 -600981194 1 351594 751311220 1 27428 454875485 1 435918 -341772073 1 382468 674611644 1 61523 312320178 1 215262 672090345 1 278922 -573278642 2 -575458309 1 310338 -493159697 1 423159 -920745267 2 -266486797 3 367763153 1 353400 -607164189 1 192866 1283313...
output:
1089463
result:
ok single line: '1089463'
Test #5:
score: 0
Accepted
time: 42ms
memory: 9276kb
input:
482013 91226 4 725259386 1 43639 194616618 4 -37234157 1 133414 -574368751 1 86430 -490776890 1 41779 -149936319 1 155135 -789189968 1 23506 90866624 1 173870 866781461 1 357433 -571999918 1 87765 -307392425 5 175104 1 230280 -534700699 1 246779 348430587 4 614286356 1 455152 -217613300 1 91751 62524122 4 950655490 1 71993 997048198 1 150586 83509358 1 295661 816414465 1 236884 710578132 1 120879 -697151469 1 87732 71949669 1 376785 -37869495 1 432182 -160890649 1 377487 65037159 5 151088 1 4766...
output:
2809378
result:
ok single line: '2809378'
Subtask #2:
score: 50
Accepted
Test #6:
score: 50
Accepted
time: 219ms
memory: 9860kb
input:
932633695 99894 1 817597654 58755520 1 830426120 -575569935 1 219698976 11255802 6 1 879216899 -243126660 4 778062635 1 614037672 -8450346 1 867388106 702693200 1 383979273 190017535 6 1 31373926 826414468 1 498056404 219646389 4 -534017693 1 364133037 733160350 2 -117264984 2 768406768 6 1 161326166 186902519 1 91199719 509313838 3 -866688044 4 -749252852 5 725422756 4 -135186037 1 829412731 -499231110 1 192705254 -967752478 3 -57968668 1 509203600 -53503710 1 380557098 834931312 1 490319936 -6...
output:
6837626
result:
ok single line: '6837626'
Test #7:
score: 0
Accepted
time: 188ms
memory: 9332kb
input:
957779956 94827 3 601355317 1 45079147 38155506 1 231631228 -362057428 6 2 -283829750 6 1 577666590 -691353274 1 205440460 -667647306 1 949397227 -3792339 1 653527564 828820694 1 491521243 915189166 3 -230329676 1 268381062 597296274 4 12779460 1 599484650 351024349 1 896651645 722621340 1 134125930 810953614 1 464298560 75698564 5 298424688 6 1 39254714 843092470 1 253157664 -685153262 1 174763189 -461497504 5 476587487 1 274557040 562236605 5 932842991 6 1 43808527 -358352611 1 615231282 -2153...
output:
4070758
result:
ok single line: '4070758'
Test #8:
score: 0
Accepted
time: 196ms
memory: 9628kb
input:
987958964 92325 2 -468910483 6 1 510389535 900881564 4 -943881278 1 120113253 5273740 1 401108682 -866524220 1 108908755 -622968084 1 690649880 -664653909 6 1 406048569 930927819 5 688114677 4 -245255661 5 105555975 1 353750321 -466163361 5 927730102 6 5 534739635 5 444272952 1 66866280 470469397 1 977893679 831668192 1 160978879 738858186 5 193586564 1 360541563 913783192 3 -599765214 1 754539363 -596882989 6 2 372889374 5 217116695 3 116284850 1 56890085 720477656 1 984056269 231141492 1 96130...
output:
7152858
result:
ok single line: '7152858'
Test #9:
score: 0
Accepted
time: 206ms
memory: 9800kb
input:
913105224 97665 1 588154473 218605071 1 628019257 213691408 6 2 678329170 2 -538647151 1 545477538 -779883649 1 799854288 -111616832 1 26866293 32675018 2 -340866521 1 124213553 384460066 1 775180734 414347048 2 123715231 1 628324808 -102971256 1 214563428 8068862 1 402502072 -706040775 1 659051837 -612536493 2 623183446 1 887844584 -239109889 1 583768900 461116851 1 205699630 -812731851 1 677636134 564597147 1 5833978 853194161 1 68883283 406530524 1 653164646 197744956 6 1 284779335 -532095296...
output:
9405271
result:
ok single line: '9405271'
Test #10:
score: 0
Accepted
time: 189ms
memory: 9596kb
input:
943284232 95163 4 -852531875 1 201974707 -653053877 1 823113651 196429318 3 337869540 1 647936647 114651757 1 593910554 120551408 1 315182996 -77867126 1 812178266 287556917 1 697126470 302117687 1 156012320 687964917 1 670615234 784564862 1 361379363 510732694 3 676262960 1 770979443 -642438266 1 142333942 -313359936 1 332502166 -412286270 1 333145078 908779306 1 164276554 -980666586 1 835971109 -371615467 1 241425357 458500894 3 168748376 1 102529817 731856225 1 401303829 721018569 6 1 3145424...
output:
1705627
result:
ok single line: '1705627'