QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#78372#4894. 学姐买瓜bear01310 2ms5552kbC++142.5kb2023-02-18 10:08:532023-02-18 10:08:54

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:08:54]
  • 评测
  • 测评结果:0
  • 用时:2ms
  • 内存:5552kb
  • [2023-02-18 10:08:53]
  • 提交

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 upd(int tl, int tr, int to){
	if(tl > tr) return ;
	//cout << "upd " << tl << " " << tr << " " << to << endl;
	int bl = tl/B, br = tr/B, bt = to/B;
	if(bl == br){
		pushdown(bl);
		for(int i = tl; i <= tr; ++i){
			nxt[i] = to;
			if(bt == bl)
				oto[i] = oto[to], odis[i] = odis[to]+1;
			else
				oto[i] = to, odis[i] = 1;
		}
	} else {
		pushdown(bl), pushdown(br);
		for(int i = tl; i < (bl+1)*B; ++i)
			nxt[i] = oto[i] = to, odis[i] = 1;
		for(int i = bl+1; i < br; ++i)
			tag[i] = to;
		for(int i = br*B; i <= tr; ++i){
			nxt[i] = to;
			if(bt == br)
				oto[i] = oto[to], odis[i] = odis[to]+1;
			else
				oto[i] = to, odis[i] = 1;
		}
	}
}

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;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

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

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: -20
Wrong Answer
time: 0ms
memory: 5488kb

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
4
2
0
3
0
2
0
2
3
2
0
0
1
3
2
0
3
5
1
0
1
1
3
0
7
0
7
1
3
1
6
1
4
7
2
2
0
4
3
2
7
3
0
7
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:

wrong answer 50th lines differ - expected: '5', found: '4'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #2:

0%