QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#388096 | #6155. 奇怪的计算器 | Ecec243 | 100 ✓ | 52ms | 16144kb | C++23 | 3.1kb | 2024-04-13 11:34:30 | 2024-04-13 11:34:31 |
Judging History
answer
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
const int N = 100005;
typedef long long ll;
using namespace std;
int m, L, R, n, op[N], ans[N], num[N];
char s[104];
struct node
{
int v, id;
bool operator < (const node &p) const
{
return v < p.v;
}
} a[N];
struct Tree { ll mn, mx, p1, p2, p3; } t[N << 2];
template < typename T >
inline T read()
{
T x = 0, w = 1; char c = getchar();
while(c < '0' || c > '9') { if(c == '-') w = -1; c = getchar(); }
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * w;
}
void pushup(int p) { t[p].mn = t[p << 1].mn, t[p].mx = t[p << 1 | 1].mx; }
void pushtag(int p, int l, int r, ll p1, ll p2, ll p3)
{
t[p].p1 *= p1, t[p].p2 = t[p].p2 * p1 + p2, t[p].p3 = t[p].p3 * p1 + p3;
t[p].mn = t[p].mn * p1 + p2 * a[l].v + p3;
t[p].mx = t[p].mx * p1 + p2 * a[r].v + p3;
}
void pushdown(int p, int l, int r)
{
if(t[p].p1 != 1 || t[p].p2 || t[p].p3)
{
int mid = (l + r) >> 1;
pushtag(p << 1, l, mid, t[p].p1, t[p].p2, t[p].p3);
pushtag(p << 1 | 1, mid + 1, r, t[p].p1, t[p].p2, t[p].p3);
t[p].p1 = 1, t[p].p2 = 0, t[p].p3 = 0;
}
}
void build(int p, int l, int r)
{
t[p].p1 = 1;
if(l == r) return (void) (t[p].mn = t[p].mx = a[l].v);
int mid = (l + r) >> 1;
build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r);
pushup(p);
}
void modifymn(int p, int l, int r)
{
if(l == r) return pushtag(p, l, r, 0, 0, L);
pushdown(p, l, r);
int mid = (l + r) >> 1;
if(t[p << 1 | 1].mn < L)
pushtag(p << 1, l, mid, 0, 0, L), modifymn(p << 1 | 1, mid + 1, r);
else modifymn(p << 1, l, mid);
pushup(p);
}
void modifymx(int p, int l, int r)
{
if(l == r) return pushtag(p, l, r, 0, 0, R);
pushdown(p, l, r);
int mid = (l + r) >> 1;
if(t[p << 1].mx > R)
pushtag(p << 1 | 1, mid + 1, r, 0, 0, R), modifymx(p << 1, l, mid);
else modifymx(p << 1 | 1, mid + 1, r);
pushup(p);
}
void query(int p, int l, int r)
{
if(l == r) return (void) (ans[a[l].id] = t[p].mn);
pushdown(p, l, r);
int mid = (l + r) >> 1;
query(p << 1, l, mid), query(p << 1 | 1, mid + 1, r);
pushup(p);
}
int main()
{
m = read <int> (), L = read <int> (), R = read <int> ();
for(int i = 1; i <= m; i++)
{
scanf("%s", s + 1), num[i] = read <int> ();
if(s[1] == '+') op[i] = 1;
else if(s[1] == '-') op[i] = 1, num[i] = -num[i];
else if(s[1] == '*') op[i] = 2;
else op[i] = 3;
}
n = read <int> ();
for(int i = 1; i <= n; i++) a[i].v = read <int> (), a[i].id = i;
sort(a + 1, a + n + 1), build(1, 1, n);
for(int i = 1; i <= m; i++)
{
if(op[i] == 1) pushtag(1, 1, n, 1, 0, num[i]);
else if(op[i] == 2) pushtag(1, 1, n, num[i], 0, 0);
else if(op[i] == 3) pushtag(1, 1, n, 1, num[i], 0);
if(t[1].mn < L) modifymn(1, 1, n);
if(t[1].mx > R) modifymx(1, 1, n);
}
query(1, 1, n);
for(int i = 1; i <= n; i++) printf("%d\n", ans[i]);
return 0;
}
詳細信息
Test #1:
score: 10
Accepted
time: 1ms
memory: 3940kb
input:
50 17 3237 + 221 - 95 - 134 - 6 - 7 + 221 - 130 + 56 + 52 + 30 - 118 - 90 + 179 + 39 + 5 + 4 - 19 - 83 + 5 - 64 - 147 - 159 + 1488 + 826 + 67 + 244 - 2384 + 1798 - 576 - 1206 - 342 - 27 - 7 + 2604 - 584 + 72 - 2112 - 1 - 1 + 2215 + 565 + 39 + 66 + 70 - 1470 - 749 - 604 + 2144 + 257 - 2034 50 661 357...
output:
779 516 781 781 781 542 781 781 781 781 516 781 781 781 781 781 781 781 516 781 516 781 781 653 781 781 781 781 516 781 733 781 781 517 781 516 781 781 781 781 781 781 781 781 781 781 781 781 781 516
result:
ok 50 numbers
Test #2:
score: 10
Accepted
time: 6ms
memory: 9684kb
input:
2000 23 654321 + 37127 + 13962 - 32555 - 18339 + 51647 - 18071 + 1766 - 24138 - 6041 + 107 - 4759 - 51 - 133 - 43 + 45753 + 7826 + 236 - 6318 - 22272 - 9124 + 23914 + 466 - 10692 + 852 + 17398 - 38614 + 12368 + 11911 - 24016 + 6983 + 21824 + 8343 - 6253 + 9239 + 286 + 2058 + 1399 + 46 - 15277 - 3359...
output:
652680 652680 555670 552947 552947 652680 652680 652680 552947 652680 644308 552947 652680 552947 652680 652680 552947 652680 552947 652680 652680 652680 652680 652680 652680 652680 552947 652680 652680 605193 652680 624262 652680 644779 652680 652680 652680 562611 652680 652680 552947 652680 652680...
result:
ok 60000 numbers
Test #3:
score: 10
Accepted
time: 15ms
memory: 15356kb
input:
3000 23 999997 + 17187 + 64111 - 53152 - 11649 + 13263 + 15352 - 20175 + 8540 - 14920 - 3223 + 53108 + 10251 - 78562 + 20238 + 59154 - 17532 - 39890 + 6612 - 17440 + 87051 - 17207 - 51925 + 70723 - 76332 - 5397 + 63867 + 3929 - 26621 + 25944 + 12409 + 2143 + 83 - 40761 - 17206 - 9812 + 54757 + 4362 ...
output:
317925 317925 317925 317925 136545 197585 317925 276145 317925 317925 317925 317925 317925 317925 317925 197156 317925 178558 317925 136545 317925 317925 317925 317925 317925 317925 193688 317925 317925 317925 317925 317925 317925 317925 317925 317925 317925 198802 317925 317925 138044 317925 317925...
result:
ok 100000 numbers
Test #4:
score: 10
Accepted
time: 17ms
memory: 15396kb
input:
3000 10 999990 * 6 + 706 + 65737 - 55917 - 1062 + 56854 - 14155 + 8018 + 8204 - 48055 + 5350 - 2976 - 14858 + 67134 - 42231 + 44694 - 19720 + 34377 + 3496 - 30882 - 32080 + 39294 + 16169 + 5192 + 5654 + 636 - 95666 + 74913 + 10826 + 4914 - 13356 + 13356 + 5134 + 78 - 54199 + 5590 + 2667 + 30649 + 13...
output:
899122 899122 899122 899122 899122 899122 899122 899122 899122 899122 899122 45486 899122 899122 899122 899122 899122 899122 899122 899122 45486 899122 899122 899122 899122 899122 899122 899122 899122 899122 899122 899122 899122 899122 899122 899122 899122 899122 899122 45486 899122 899122 45486 899...
result:
ok 100000 numbers
Test #5:
score: 10
Accepted
time: 18ms
memory: 15332kb
input:
3000 10 999990 - 1 * 4 + 63021 - 16361 - 579 + 77341 + 272113 - 287836 - 91529 - 3538 - 9133 - 3201 + 396919 - 387722 - 8573 - 11 + 64704 + 64107 - 35169 - 88978 - 3220 + 113206 + 282816 + 806 + 344 + 328 + 49 - 375735 - 12644 - 822 - 3000 - 1310 + 165552 + 93184 + 47114 + 42302 - 295082 - 10936 - 2...
output:
10 888234 888234 888234 888234 888234 888234 888234 888234 888234 888234 888234 10 888234 888234 888234 888234 888234 888234 888234 888234 888234 888234 888234 888234 888234 888234 888234 888234 888234 888234 888234 888234 888234 888234 888234 888234 888234 888234 888234 888234 888234 888234 888234 ...
result:
ok 100000 numbers
Test #6:
score: 10
Accepted
time: 22ms
memory: 9932kb
input:
50000 17 87654321 - 30495112 @ 44 - 1618354 - 4935460 - 81100490 @ 15 - 4621567 - 4131441 + 2239064 - 4664982 - 5261041 - 31734005 + 3393352 - 2557698 - 835654 @ 35 + 1517054 + 5097530 - 74361774 @ 18 - 1794886 @ 25 @ 74 - 7073004 + 5695024 + 3474263 - 87654304 @ 31 + 5665143 @ 7 - 8733339 @ 14 @ 42...
output:
87654321 87654321 87654321 87654321 43722331 87654321 87654321 5516745 77213445 82555013 75957049 67337553 87654321 78463925 31892419 56161939 16977313 82414479 35906135 87654321 47339965 56769373 87654321 59313253 1266447 87654321 55071423 30019599 31870669 11645431 87654321 41833909 63949773 87654...
result:
ok 50000 numbers
Test #7:
score: 10
Accepted
time: 52ms
memory: 16084kb
input:
100000 13 987654321 - 10750841 - 183129314 - 430367220 + 15503994 @ 3 - 8321141 + 12995054 @ 221 + 16062873 + 4793407 + 8795001 - 987654308 @ 125 + 15340565 + 16171744 @ 321 + 12353378 - 2643436 - 985010872 @ 90 + 1155314 + 14944187 - 9936629 - 969662012 @ 96 - 760194528 @ 728 + 2629761 - 10615963 +...
output:
522751275 984808405 758474755 910637785 968756905 893505055 817921825 980759995 958425535 814956355 983926105 926381515 946344355 937174225 939502135 400761786 355793097 937533295 215061315 984942685 960238345 897496225 881494135 311788863 954260785 873035005 962805295 939315985 799268065 573716874 ...
result:
ok 100000 numbers
Test #8:
score: 10
Accepted
time: 48ms
memory: 16088kb
input:
100000 1 1000000000 - 6148649 + 4246045 @ 260 - 10509715 - 2092137 - 90007045 + 8130601 @ 21 @ 98 - 385408579 - 614591420 @ 59 + 13957524 + 776879 @ 100 + 16447684 + 8365049 - 197003477 - 385644093 @ 151 - 211076784 + 9580525 + 19240964 - 97075353 - 228768754 @ 47 + 18818956 + 912208 @ 477 + 1630086...
output:
1 32347418 246892043 19054381 687698715 827102634 632908631 819429030 535347030 517866721 426683066 724125056 648310757 788781622 622411609 45985614 330980541 690724968 344148318 26293837 189800488 783321123 321158694 731477627 641816308 566228122 10542400 473560099 581991396 565204003 860041282 822...
result:
ok 100000 numbers
Test #9:
score: 10
Accepted
time: 44ms
memory: 16104kb
input:
100000 31 999999998 - 4373212 @ 95 - 885052837 * 17428467 + 164380520 - 89443838 - 140653055 - 37078398 - 437487675 * 9379847 * 3 @ 46 - 999999967 @ 103 - 317691301 + 192469409 * 3 - 14555621 + 129627009 - 198973453 - 801026514 @ 194 + 105440551 - 314928347 - 105872955 - 225288311 - 65124557 - 45331...
output:
99684319 969062793 969062793 872217327 566700687 244438175 969062793 368469511 969062793 404355439 423839423 342278359 825526423 817761887 969062793 969062793 684735487 969062793 710788631 969062793 969062793 969062793 969062793 969062793 245728087 969062793 969062793 969062793 689090903 721611495 9...
result:
ok 100000 numbers
Test #10:
score: 10
Accepted
time: 49ms
memory: 16144kb
input:
100000 1 999999999 - 299550059 * 84345505 + 18941515 + 30727905 @ 76 - 11819870 - 32197705 - 140374861 @ 121 + 10343129 - 999999998 * 817778790 - 817778789 @ 8 * 18 - 6789525 - 8882723 - 425894121 * 2 - 232263520 + 2492192 - 2492192 @ 71 + 1635871 - 999999998 * 829443584 - 133336147 - 496881877 @ 11...
output:
690168554 690168554 690168554 690168554 690168554 690168554 690168554 690168554 690168554 690168554 690168554 690168554 690168554 690168554 690168554 690168554 690168554 690168554 690168554 690168554 690168554 690168554 690168554 690168554 690168554 690168554 690168554 690168554 690168554 690168554 ...
result:
ok 100000 numbers