QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#253098#7311. Welcome to ICPCCamp 2017PetroTarnavskyi#AC ✓157ms25660kbC++202.3kb2023-11-16 17:50:232023-11-16 17:50:23

Judging History

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

  • [2023-11-16 17:50:23]
  • 评测
  • 测评结果:AC
  • 用时:157ms
  • 内存:25660kb
  • [2023-11-16 17:50:23]
  • 提交

answer

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

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); i--)
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

const int mod = 1e9 + 7;
int add(int a, int b)
{
	return a + b < mod ? a + b : a + b - mod;
}
int sub(int a, int b)
{
	return a - b >= 0 ? a - b : a - b + mod;
}
int mult(int a, int b)
{
	return (LL)a * b % mod;
}
int binpow(int a, int n)
{
	int res = 1;
	while(n)
	{
		if(n & 1)
			res = mult(res, a);
		a = mult(a, a);
		n /= 2;
	}
	return res;
}

struct Fenwick
{
	int n;
	vector<LL> v;
	
	void init(int _n)
	{
		n = _n;
		v.assign(n, 0);
	}
	
	void upd(int i, int x)
	{
		for (; i < n; i |= (i + 1))
			v[i] = add(v[i], x);
	}
	
	LL query(int i)
	{
		LL ans = 0;
		for (; i >= 0; i = (i & (i + 1)) - 1)
			ans = add(ans, v[i]);
		return ans;
	}	
};


const int N = 1 << 18;
VI r[N];

int level[N], cnt[N];

void solve(int n, int m)
{
	FOR(i, 0, n + 1)
	{
		int k;
		if(i != n)
			cin >> k;
		else
			k = m;
		r[i].resize(k);
		FOR(j, 0, k)
			cin >> r[i][j];
	}
	FOR(i, 0, m + 1)
		level[i] = -1;
		
	set<int> poses;
	FOR(i, 0, n)
		poses.insert(i);
	set<int> uniq;
	
	int lvl = 0;
	while(SZ(poses))
	{
		cnt[lvl] = 0;
		VI del;
		for(int i : poses)
		{
			int cur = r[i][lvl];
			if(!uniq.count(cur))
			{
				uniq.insert(cur);
				level[cur] = lvl;
				cnt[lvl]++;
			}	
		
			if(lvl + 1 == SZ(r[i]))
				del.PB(i);
		}
		
		for(int i : del)
			poses.erase(i);
		lvl++;
	}
	Fenwick F;
	F.init(lvl);
	FOR(lv, 0, lvl)
		F.upd(lv, sub(binpow(2, cnt[lv]), 1));
	
	int ans = m + 1;
	FOR(i, 0, m)
	{
		int val = r[n][i];
		int lv = level[val];
		if(lv == -1)
		{
			ans = add(ans, F.query(lvl - 1));
			continue;
		}
		F.upd(lv, sub(1, binpow(2, cnt[lv])));
		cnt[lv]--;
		F.upd(lv, sub(binpow(2, cnt[lv]), 1));
		
		ans = add(ans, F.query(lv));
	}
	cout << ans << "\n";
}



int main()
{
    ios::sync_with_stdio(0); 
    cin.tie(0);
	
	int n, m;
	while(cin >> n >> m)
		solve(n, m);




	
	
	return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 10904kb

input:

2 3
2 1 3
3 2 1 3
2 1 3
0 3
1 2 3

output:

5
4

result:

ok 2 number(s): "5 4"

Test #2:

score: 0
Accepted
time: 44ms
memory: 10884kb

input:

3 16
1 7
1 16
1 4
14 10 8 1 4 13 5 9 7 12 2 6 3 16 11 15
10 16
2 10 6
2 12 1
3 16 4 1
2 11 5
1 14
1 9
4 14 10 4 13
2 7 14
1 15
1 14
6 15 12 9 5 14 10 16 4 7 11 2 3 8 1 13
6 15
2 15 5
2 10 13
1 11
2 6 10
3 4 9 12
3 13 1 10
7 3 4 1 10 12 13 6 9 14 15 11 5 2 8
5 6
1 6
1 6
1 4
5 4 5 1 2 3
3 4 6 3
3 5 4 ...

output:

62
570
275
17
17
4658
38
49
964
208
37
69
2
4
32
26
15
133
42
26
68
19
4
35
32
2
4
24
33
13
2
36
4
97
20
41
2
22
35
32
22
24
10
21
31
187
39
5
18
17
90
64
39
18
57
6
37
79
64
56
61
7
64
38
32
26
7
16
78
4
13
13
34
16
68
12
8
95
124
87
4
2
34
4
35
13
8
128
79
23
59
37
27
9
149
84
8
13
152
8
32
36
16
...

result:

ok 20000 numbers

Test #3:

score: 0
Accepted
time: 37ms
memory: 10584kb

input:

7 43
2 20 8
1 28
2 26 42
2 32 27
1 1
1 24
1 5
2 27 9 19 25 31 33 21 26 30 5 38 39 18 29 28 22 11 40 15 35 13 23 24 4 17 34 16 7 36 1 41 3 43 12 32 20 14 37 6 8 10 42
25 7
1 5
1 1
1 1
1 1
1 4
1 3
3 2 3 7
2 5 3
1 1
1 7
1 5
2 1 4
1 3
1 6
3 7 1 6
1 3
3 3 7 2
1 1
1 5
2 4 5
2 7 6
2 6 4
1 4
1 7
3 6 3 2
7 6...

output:

1631
128
662023095
811
1220558
12237484
157
23
423317
533
6144
446
16
92
464
66
3717
335
269
143
1149
8
87
462
8
146
273
60
2750
3121
25730
8300
453
71
8
225
179
1024
2133
80
1869
210
5
520
145
6406
397
448
2
5385
374
2
1568
1340
625
2109
1906
15
134293
207
452
2
534
207
338
747
141
834
8183
396
613...

result:

ok 5000 numbers

Test #4:

score: 0
Accepted
time: 46ms
memory: 10632kb

input:

332 114
1 56
1 49
1 61
2 104 103
1 21
1 80
2 48 9
4 22 60 54 76
3 40 1 91
1 41
1 33
1 16
1 24
1 110
2 81 54
1 85
2 87 83
1 39
1 37
1 80
2 76 30
2 77 106
1 21
2 65 32
1 58
1 49
1 39
2 100 22
1 102
2 88 30
1 105
1 113
2 72 99
4 11 28 90 68
2 100 70
4 106 69 33 37
1 43
2 64 54
2 87 72
2 106 114
2 106 6...

output:

883483423
376235721
57578466
745793211
322521185
896987515
307265211
625207906
69260834
10142
728040081
637898435
647006134
388201470
154859
657704184
481217084
201985264
708777
793575511
777386063
1123
454
765604361
149499192
827505894
31907427
3786811
23077
868980658
310604661
7833224
50863221
217...

result:

ok 500 numbers

Test #5:

score: 0
Accepted
time: 54ms
memory: 12800kb

input:

621 2007
1 1465
1 1362
1 1493
2 628 1345
1 1446
1 985
1 1179
2 384 1567
1 1076
2 1234 321
1 543
1 1847
3 282 1492 1563
1 787
1 1027
1 242
2 1094 514
2 860 1041
2 1853 1191
2 912 452
4 1312 834 1059 486
1 1192
1 329
1 1503
3 1793 1882 1580
2 444 1749
1 1151
2 938 1059
2 399 1064
1 385
2 871 1190
2 13...

output:

434218100
843108075
900298261
176519701
72793001
855849581
227252458
198516093
134099126
908583582
49833642
174002989
103644691
715492397
485920845
145586002
49642063
648694435
488579377
73382381
389591312
423770169
493768501
386823481
760789999
45124599
347280587
127580523
4364
467535190
830713404
...

result:

ok 50 numbers

Test #6:

score: 0
Accepted
time: 157ms
memory: 25660kb

input:

126405 200000
1 181938
2 56300 7338
1 101988
2 8883 136306
1 98423
1 76781
1 31908
1 49420
2 114001 32260
1 149532
1 147565
2 174485 110547
2 33937 60001
1 138807
1 129263
3 95277 116816 159765
1 93820
1 119526
2 176428 158503
2 109228 74534
1 145027
2 50256 163731
1 196627
2 150778 173871
1 177984
...

output:

661326989

result:

ok 1 number(s): "661326989"

Test #7:

score: 0
Accepted
time: 115ms
memory: 18324kb

input:

32764 200000
4 32669 2034 137677 157374
1 120487
19 90939 147780 195220 143751 79105 72149 54500 23013 17141 9172 172475 45866 126229 77692 75672 70812 47786 180432 122613
17 178624 103070 182049 51065 105374 31234 15188 93118 164080 21460 30935 151825 46711 152525 175812 32597 180538
3 138911 28081...

output:

885398592

result:

ok 1 number(s): "885398592"

Test #8:

score: 0
Accepted
time: 115ms
memory: 18148kb

input:

17234 200000
3 152748 130305 18708
20 107564 90964 96824 105786 132889 111245 5908 127664 16333 137438 186144 171482 150527 172709 151007 156991 171865 43636 82060 197008
6 190295 48278 86033 93148 5431 18077
7 42183 85071 14314 83272 164967 190587 140044
8 135789 172485 96645 68432 53983 159752 188...

output:

35359153

result:

ok 1 number(s): "35359153"

Test #9:

score: 0
Accepted
time: 93ms
memory: 18652kb

input:

2686 200000
3 34905 106578 123527
24 197549 151584 57127 52102 138903 83267 194979 49629 29897 2005 184951 28348 119372 47746 36186 54079 178911 100829 158578 165713 191081 175518 103586 146210
113 137937 137689 158028 28506 58619 127513 17384 166089 164564 117519 193809 105076 81123 22337 53875 793...

output:

266652290

result:

ok 1 number(s): "266652290"

Test #10:

score: 0
Accepted
time: 95ms
memory: 17808kb

input:

369 200000
30 180553 17474 132462 64502 35446 190112 46372 98267 40928 107615 159636 170883 84846 108520 27238 51577 150692 185368 85599 33459 99609 140902 21867 145420 196243 27664 78345 135923 19159 31023
97 53152 102912 29197 130411 141629 24584 106082 114440 86121 41665 132713 121142 107047 1504...

output:

351500019

result:

ok 1 number(s): "351500019"

Test #11:

score: 0
Accepted
time: 99ms
memory: 20524kb

input:

11 200000
895 61784 78254 48407 195251 33463 139947 188001 158222 62008 104908 2112 175239 138856 165697 191089 14887 19276 63301 30908 118378 193617 142702 44334 157185 55461 7100 189771 8291 66241 131628 125805 29784 164895 8624 42578 36178 67912 51140 95357 144704 3308 26 153020 158466 20404 1235...

output:

616668026

result:

ok 1 number(s): "616668026"

Extra Test:

score: 0
Extra Test Passed