QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#388096#6155. 奇怪的计算器Ecec243100 ✓52ms16144kbC++233.1kb2024-04-13 11:34:302024-04-13 11:34:31

Judging History

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

  • [2024-04-13 11:34:31]
  • 评测
  • 测评结果:100
  • 用时:52ms
  • 内存:16144kb
  • [2024-04-13 11:34:30]
  • 提交

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