QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#78373#4894. 学姐买瓜bear01310 2ms5640kbC++142.6kb2023-02-18 10:18:012023-02-18 10:18:03

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-18 10:18:03]
  • 评测
  • 测评结果:0
  • 用时:2ms
  • 内存:5640kb
  • [2023-02-18 10:18:01]
  • 提交

answer

#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; ++i)
using namespace std;
typedef pair<int, int> pii;
const int inf = 0x3f3f3f3f;

int n;
const int N = 300300, B = 555;
set< pii > st;
int tag[N/B + 10];
int nxt[N], oto[N], odis[N];
void pushdown(int bid){
	if(tag[bid] < 0)
		return ;
	int l = bid*B, r = min((bid+1)*B, n);
	for(int i = l; i < r; ++i)
		nxt[i] = oto[i] = tag[bid], odis[i] = 1;
	tag[bid] = -1;
}
void recalc(int bid){
	int l = bid*B, r = min((bid+1)*B, n);
	for(int i = r-1; i >= l; --i){
		if(nxt[i] >= r)
			oto[i] = nxt[i], odis[i] = 1;
		else
			oto[i] = oto[nxt[i]], odis[i] = odis[nxt[i]] + 1;
	}
}

void upd(int tl, int tr, int to){
	if(tl > tr) return ;
	//cout << "upd " << tl << " " << tr << " " << to << endl;
	int bl = tl/B, br = tr/B;
	if(bl == br){
		pushdown(bl);
		for(int i = tl; i <= tr; ++i)
			nxt[i] = to;
		recalc(bl);
	} else {
		pushdown(bl), pushdown(br);
		for(int i = tl; i < (bl+1)*B; ++i)
			nxt[i] = to;
		recalc(bl);
		for(int i = bl+1; i < br; ++i)
			tag[i] = to;
		for(int i = br*B; i <= tr; ++i)
			nxt[i] = to;
		recalc(br);
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	memset(tag, -1, sizeof(tag));

	int m;
	cin >> m >> n;
	rep(i, n)
		nxt[i] = oto[i] = inf, odis[i] = 0;
	st.emplace(-1, -1);
	st.emplace(n, n);
	while(m--){
		int tp;
		cin >> tp;
		if(tp == 1){
			int l, r;
			cin >> l >> r;
			--l, --r;
			auto itr = st.lower_bound(make_pair(l, n+1));
			if(itr->second <= r) continue;
			--itr;
			int updl = itr->first + 1;
			while(r <= itr->second){
				auto pre = prev(itr);
				updl = pre->first + 1;
				st.erase(itr);
				itr = pre;
			}
			upd(updl, l, r+1);
			st.emplace(l, r);
			//for(auto it = st.begin(); it != st.end(); ++it)
			//	cout << "(" << it->first << " " << it->second << ") ";
			//cout << endl;
			//rep(i, (n-1)/B+1)
			//	cout << " " << tag[i]; cout << endl;
			//rep(i, n)
			//	cout << nxt[i] << " "; cout << endl;
			//rep(i, n)
			//	cout << oto[i] << " "; cout << endl;
			//rep(i, n)
			//	cout << odis[i] << " "; cout << endl;
		} else {
			int l, r;
			cin >> l >> r;
			--l, --r;
			int np = l, ans = 0;
			while(1){
				int bel = np/B;
				if(tag[bel] >= 0){
					if(tag[bel] <= r+1)
						++ans, np = tag[bel];
					else
						break;
				} else {
					if(oto[np] <= r+1)
						ans += odis[np], np = oto[np];
					else {
						if(nxt[np] <= r+1)
							++ans, np = nxt[np];
						else
							break;
					}
				}
			}
			cout << ans << "\n";
		}
	}

	return 0;
}

詳細信息

Subtask #1:

score: 0
Time Limit Exceeded

Test #1:

score: 20
Accepted
time: 2ms
memory: 5388kb

input:

11 13
2 4 4
1 11 12
1 1 5
1 2 3
1 2 10
2 2 8
1 6 6
2 2 10
1 6 11
2 2 3
2 2 13

output:

0
1
2
1
3

result:

ok 5 lines

Test #2:

score: 0
Accepted
time: 1ms
memory: 5640kb

input:

2000 2000
2 66 273
1 475 1570
2 51 958
2 731 1771
1 1286 1627
1 37 892
1 529 890
2 155 1486
1 87 1815
1 576 1872
2 1269 1515
2 1521 1794
2 634 1887
2 204 1668
1 351 1679
2 1571 1599
1 243 681
2 1 2000
2 1 2000
2 564 648
2 1215 1807
2 466 1617
1 1119 1348
1 497 886
2 1358 1487
2 173 1974
1 401 1294
2...

output:

0
0
0
1
0
0
1
2
0
2
2
0
1
1
0
2
1
1
0
1
0
1
0
0
1
2
1
1
1
2
1
1
0
0
2
2
0
2
2
0
1
3
0
0
4
0
0
2
2
5
2
0
4
0
2
0
2
3
3
0
0
1
3
2
0
3
6
1
0
1
1
4
0
8
0
8
1
3
1
8
1
4
9
2
2
0
4
5
2
9
3
0
9
1
3
8
9
1
0
7
0
8
5
7
0
1
0
6
10
2
6
0
1
0
6
4
6
5
4
4
4
0
10
0
6
2
8
9
1
10
5
7
8
10
1
10
8
5
2
6
1
5
10
8
10
5
3...

result:

ok 1020 lines

Test #3:

score: 0
Accepted
time: 1ms
memory: 5452kb

input:

2000 2000
2 66 273
1 475 1570
2 51 958
2 731 1771
1 1286 1627
1 37 892
1 529 890
2 155 1486
1 87 1815
1 576 1872
2 1269 1515
2 1521 1794
2 634 1887
2 204 1668
1 351 1679
2 1571 1599
1 243 681
2 1 2000
2 1 2000
2 564 648
2 1215 1807
2 466 1617
1 1119 1348
1 497 886
2 1358 1487
2 173 1974
1 401 1294
2...

output:

0
0
0
1
0
0
1
2
0
2
2
0
1
1
0
2
1
1
0
1
0
1
0
0
1
2
1
1
1
2
1
1
0
0
2
2
0
2
2
0
1
3
0
0
4
0
0
2
2
5
2
0
4
0
2
0
2
3
3
0
0
1
3
2
0
3
6
1
0
1
1
4
0
8
0
8
1
3
1
8
1
4
9
2
2
0
4
5
2
9
3
0
9
1
3
8
9
1
0
7
0
8
5
7
0
1
0
6
10
2
6
0
1
0
6
4
6
5
4
4
4
0
10
0
6
2
8
9
1
10
5
7
8
10
1
10
8
5
2
6
1
5
10
8
10
5
3...

result:

ok 1020 lines

Test #4:

score: 0
Accepted
time: 2ms
memory: 5604kb

input:

14 11
1 1 8
1 4 11
2 4 8
1 2 7
1 7 11
2 2 9
1 6 10
1 2 6
1 8 10
1 2 6
2 9 10
1 9 9
1 3 10
1 2 4

output:

0
1
0

result:

ok 3 lines

Test #5:

score: -20
Time Limit Exceeded

input:

2000 2000
1 1589 1640
1 1741 1765
2 191 1596
1 426 493
2 1434 1606
1 925 955
2 589 1148
2 1347 1608
2 686 1516
1 1535 1563
1 1835 1841
1 1513 1537
2 30 1710
2 123 171
2 1 2000
2 128 1310
2 270 879
1 1918 1941
2 965 1951
2 176 1452
1 1391 1421
1 614 664
2 1 2000
1 296 328
1 1378 1402
1 29 47
1 92 123...

output:


result:


Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #2:

0%