QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#78372 | #4894. 学姐买瓜 | bear0131 | 0 | 2ms | 5552kb | C++14 | 2.5kb | 2023-02-18 10:08:53 | 2023-02-18 10:08:54 |
Judging History
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%