QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#84453#5657. Hungry CowEnder32k9.090909 63ms116840kbC++203.7kb2023-03-06 15:08:422023-03-06 15:08:59

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-06 15:08:59]
  • 评测
  • 测评结果:9.090909
  • 用时:63ms
  • 内存:116840kb
  • [2023-03-06 15:08:42]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
using namespace std;

namespace vbzIO {
    char ibuf[(1 << 20) + 1], *iS, *iT;
    #if ONLINE_JUDGE
    #define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
    #else
    #define gh() getchar()
    #endif
    #define pc putchar
    #define pi pair<int, int>
    #define tu3 tuple<int, int, int>
    #define tu4 tuple<int, int, int, int>
    #define mp make_pair
    #define mt make_tuple
    #define fi first
    #define se second
    #define pb push_back
    #define ins insert
    #define era erase
    inline int read () {
        char ch = gh();
        int x = 0;
        bool t = 0;
        while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
        while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
        return t ? ~(x - 1) : x;
    }
    inline void write(int x) {
        if (x < 0) {
            x = ~(x - 1);
            putchar('-');
        }
        if (x > 9)
            write(x / 10);
        putchar(x % 10 + '0');
    }
}
using vbzIO::read;
using vbzIO::write;

const int maxn = 1e5 + 100;
const int mod = 1e9 + 7;
struct seg { int val, cnt, tag, lc, rc; } tr[maxn * 100];
int n, m = 1e15, tot, ans[maxn], rt[maxn << 2];
map<int, int> lst;
pi q[maxn];
vector<int> ct[maxn << 2];
 
#define ls tr[x].lc
#define rs tr[x].rc
#define mid ((l + r) >> 1)
void pushup(int x) { tr[x].cnt = tr[ls].cnt + tr[rs].cnt, (tr[x].val = tr[ls].val + tr[rs].val) % mod; }
void pushcov(int x, int l, int r) { tr[x].tag = 1, tr[x].cnt = r - l + 1, tr[x].val = (l + r) * (r - l + 1) / 2 % mod; }
void pushdown(int x, int l, int r) {
	if (!tr[x].tag) return;
	if (!ls) ls = ++tot;
	if (!rs) rs = ++tot;
	pushcov(ls, l, mid);
	pushcov(rs, mid + 1, r);
	tr[x].tag = 0;
}

void cov(int l, int r, int s, int t, int rt, int &x) {
	if (t < s) return;
	x = ++tot, tr[x] = tr[rt];
	if (s <= l && r <= t) return pushcov(x, l, r);
	pushdown(rt, l, r), pushdown(x, l, r);
	if (s <= mid) cov(l, mid, s, t, tr[rt].lc, ls);
	if (t > mid) cov(mid + 1, r, s, t, tr[rt].rc, rs);
	pushup(x);
}

int qry(int l, int r, int k, int x) {
	if (l == r) return l;
	pushdown(x, l, r);
	int suml = tr[ls].cnt;
	if ((mid - l + 1) - suml < k) return qry(mid + 1, r, k - ((mid - l + 1) - suml), rs);
	else return qry(l, mid, k, ls);
}

int sum(int l, int r, int s, int t, int x) {
	if (t < s || !x) return 0;
	if (s <= l && r <= t) return tr[x].cnt;
	pushdown(x, l, r);
	int res = 0; 
	if (s <= mid) res += sum(l, mid, s, t, ls);
	if (t > mid) res += sum(mid + 1, r, s, t, rs);
	return res;
}

void ins(int l, int r, int s, int t, int id, int x) {
	if (s <= l && r <= t) return ct[x].pb(id);
	if (s <= mid) ins(l, mid, s, t, id, x << 1);
	if (t > mid) ins(mid + 1, r, s, t, id, x << 1 | 1);
} 

void conq(int l, int r, int x, int fa) {
//	cerr << "[]: " << x << " " << l << " " << r << " " << endl;
	rt[x] = rt[fa];
	for (int i : ct[x]) {
//		cerr << sum(1, m, 1, q[i].fi - 1, rt[x]) << " ";
		int pos = qry(1, m, q[i].se + (q[i].fi - 1 - sum(1, m, 1, q[i].fi - 1, rt[x])), rt[x]);
		cov(1, m, q[i].fi, pos, rt[x], rt[x]);
//		cerr << q[i].fi << " " << q[i].se << " " << pos << endl;
	}
	if (l == r) return ans[l] = tr[rt[x]].val, void();
	conq(l, mid, x << 1, x);
	conq(mid + 1, r, x << 1 | 1, x);
}

signed main() {
	n = read();
	for (int i = 1; i <= n; i++) {
		int d = read(), b = read();
		q[i] = mp(d, b);
		if (lst[d]) ins(1, n, lst[d], i - 1, lst[d], 1);
		lst[d] = i;
	}
	for (pi p : lst) ins(1, n, p.se, n, p.se, 1); 
	conq(1, n, 1, 0);
	for (int i = 1; i <= n; i++) 
		write(ans[i]), puts("");
	return 0;
}

详细

Test #1:

score: 4.54545
Accepted
time: 1ms
memory: 16620kb

input:

3
4 3
1 5
1 2

output:

15
36
18

result:

ok 3 number(s): "15 36 18"

Test #2:

score: 4.54545
Accepted
time: 1ms
memory: 17300kb

input:

9
1 89
30 7
101 26
1 24
5 1
60 4
5 10
101 0
1 200

output:

4005
4656
7607
3482
3507
3753
4058
1107
24531

result:

ok 9 numbers

Test #3:

score: 0
Wrong Answer
time: 63ms
memory: 116840kb

input:

5000
1 255364995
414918035 212844
1 112266691
321122438 191414
1 277615842
848755093 61676
1 432591689
892259443 53755
1 263753018
173404455 173565
1 178341924
878941367 221276
1 65332960
439468128 240741
1 812238377
191076090 108732
1 180383041
927440330 112995
1 595696140
579818784 85614
1 5057816...

output:

4235118058
13699919062
16430865804
23080346774
23848027487
37568710653
22340195392
33190991314
46826211986
64180952119
49569936200
57679922407
63650994389
70624850667
41428417018
39646485217
75727441152
83230674452
45429375069
55412788567
54052678948
68076241786
59668854234
7778261020
47670415074
50...

result:

wrong answer 1st numbers differ - expected: '235118030', found: '4235118058'

Test #4:

score: 0
Runtime Error

input:

100000
1 500000000
1000000001 500000000
2000000001 500000000
3000000001 500000000
4000000001 500000000
5000000001 500000000
6000000001 500000000
7000000001 500000000
8000000001 500000000
9000000001 500000000
10000000001 500000000
11000000001 500000000
12000000001 500000000
13000000001 500000000
1400...

output:


result:


Test #5:

score: 0
Runtime Error

input:

100000
49998999950002 500000000
49997999950003 500000000
49996999950004 500000000
49995999950005 500000000
49994999950006 500000000
49993999950007 500000000
49992999950008 500000000
49991999950009 500000000
49990999950010 500000000
49989999950011 500000000
49988999950012 500000000
49987999950013 500...

output:


result:


Test #6:

score: 0
Runtime Error

input:

100000
92303348842417 121458
92270522994821 852054850
93765096269940 752161890
97779083359973 984327853
90030769679569 439157849
99462493683485 45660
95578441605501 614317411
92236129196525 474149928
96065411631989 429943696
90394247621798 382840249
89263934750729 791122796
93577089467158 99679481
9...

output:


result:


Test #7:

score: 0
Runtime Error

input:

100000
98001410246890 641673458
94816407430628 495030536
95979591652947 43208
95979591652947 183686
97163521776290 904784415
91640049592559 875129980
95914835187460 844802426
94846379383324 974270031
99639652388956 311664277
99298294827771 913614463
99476866913169 221766107
97248342663994 669489020
...

output:


result:


Test #8:

score: 0
Runtime Error

input:

100000
97338601145206 191999210
97657969728741 875988993
92559675348135 8552565
99354409480201 960853995
93648768326445 343671323
97400841247229 104463842
98844341051398 508718383
96144328794112 187050711
98030257583732 365513
92378049740181 852725611
98301676983212 360931360
99458914124366 80234576...

output:


result:


Test #9:

score: 0
Runtime Error

input:

100000
96119987448606 658315028
98644701118435 280992389
98180676447908 56168
99822794299596 237183170
94655838918825 563695131
95744558879343 686204820
93739311062176 263266841
97630990881452 96901680
98683433984282 380708175
98141920320037 147598812
98095513966598 814629225
97882900659205 55097258...

output:


result:


Test #10:

score: 0
Runtime Error

input:

100000
98169641631056 170946511
99452522210742 393032132
98797460964704 393706377
98747209012224 529219651
99152468691953 362194103
99410753036475 215295
97096873124809 1315725
96106202009957 124516158
95176405230280 853965254
99359463136784 622839995
96635771520630 550456203
96368792029394 93630831...

output:


result:


Test #11:

score: 0
Runtime Error

input:

100000
97499080763005 475255826
97499083333242 9347
97499080763005 395470349
97499924236501 4654
97499080763005 148122052
97499213182916 2365
97499080763005 544025506
97499777050346 9912
97499080763005 41736833
97499401163067 12607
97499080763005 127843558
97499125181305 7144
97499080763005 13152858...

output:


result:


Test #12:

score: 0
Runtime Error

input:

100000
98999026537234 929244389
98999182418499 5182
98999026537234 774643967
98999646433835 17857
98999026537234 760743518
98999980664456 7597
98999026537234 573421161
98999090975969 6621
98999026537234 95191521
98999947586610 17798
98999026537234 953104244
98999116462517 15643
98999026537234 100617...

output:


result:


Test #13:

score: 0
Runtime Error

input:

100000
99499024212061 630391525
99499061152079 3864
99499024212061 16505706
99499878275777 4812
99499024212061 776185964
99499757280269 12059
99499024212061 356565635
99499399237611 8902
99499024212061 972528120
99499256994518 9171
99499024212061 419476867
99499909552451 17146
99499024212061 6767939...

output:


result:


Test #14:

score: 0
Runtime Error

input:

99999
10490328589436 1000000000
13762508396295 1000000000
40632115714511 1000000000
32834989282081 1000000000
29091918306598 1000000000
24352818172350 1000000000
23447797352860 1000000000
38073075086135 1000000000
14288530509239 1000000000
36463049009868 1000000000
10562334120356 1000000000
34490016...

output:


result:


Test #15:

score: 0
Runtime Error

input:

99999
61585049539216 1000000000
58981995705940 1000000000
44247484521936 1000000000
70916218483207 1000000000
47696673638497 1000000000
60781033156530 1000000000
55859922511212 1000000000
59143999312357 1000000000
57175954090596 1000000000
71328224891428 1000000000
46047599292678 1000000000
47510666...

output:


result:


Test #16:

score: 0
Runtime Error

input:

99999
21219982576425 1000000000
42260400232639 1000000000
26412110792985 1000000000
11035481121988 1000000000
13219690258669 1000000000
19550933913223 1000000000
32679237390903 1000000000
15679803374289 1000000000
23896051833122 1000000000
20099950455987 1000000000
14778766729432 1000000000
21547991...

output:


result:


Test #17:

score: 0
Runtime Error

input:

99999
28503598869279 1000000000
32397709666940 1000000000
25833502058723 1000000000
38020841213328 1000000000
54560138759501 1000000000
42230929758874 1000000000
28972613620824 1000000000
28498598787317 1000000000
54070131397843 1000000000
22084267818956 1000000000
37776835952805 1000000000
44465973...

output:


result:


Test #18:

score: 0
Runtime Error

input:

99999
18175781548542 1000000000
40883228277118 1000000000
33828113807745 1000000000
17817771477758 1000000000
22749897023579 1000000000
18015777423352 1000000000
28920025506062 1000000000
18799798298070 1000000000
27979006765970 1000000000
17103749421004 1000000000
24329932307643 1000000000
29798042...

output:


result:


Test #19:

score: 0
Runtime Error

input:

99999
13631696063382 1000000000
19095823575649 1000000000
18048800926387 1000000000
17060779354093 1000000000
15768748767399 1000000000
30886037572930 1000000000
26814970558482 1000000000
8165534157289 1000000000
27914989206121 1000000000
34170089895536 1000000000
27764986366439 1000000000
145187181...

output:


result:


Test #20:

score: 0
Runtime Error

input:

99999
71091006018203 1000000000
42267334298998 1000000000
53421686894439 1000000000
52992676205010 1000000000
49055576058012 1000000000
70721000416119 1000000000
43151374327143 1000000000
70716000332404 1000000000
51528640431406 1000000000
65945925001029 1000000000
39524135856472 1000000000
66414932...

output:


result:


Test #21:

score: 0
Runtime Error

input:

99999
43981987091230 1000000000
41793950053258 1000000000
23385527966154 1000000000
32049759202175 1000000000
48927065970165 1000000000
26694629471843 1000000000
27661655640242 1000000000
37241867113918 1000000000
49110069037684 1000000000
20323405372655 1000000000
43304975621086 1000000000
48021052...

output:


result:


Test #22:

score: 0
Runtime Error

input:

99999
31159466866911 1000000000
28413414847308 1000000000
25948364344910 1000000000
31236468095715 1000000000
22036273821032 1000000000
24056321657736 1000000000
36031551606814 1000000000
37935581367999 1000000000
40624624246259 1000000000
18857191994835 1000000000
22179277697755 1000000000
29154428...

output:


result: