이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
void compress(vector<int> &a){
int n = a.size();
vector<pair<int,int>> b(n);
for(int i=0;i<n;i++){
b[i].first = a[i];
b[i].second = i;
}
sort(b.begin(),b.end());
a[b[0].second] = 1;
int cnt = 1;
for(int i=1;i<n;i++){
if(b[i].first == b[i-1].first){
a[b[i].second] = a[b[i-1].second];
}
else a[b[i].second] = ++cnt;
}
}
struct segTree{
int n;
vector<int> tree;
vector<pair<int,int>> lazy;
segTree(int _n){
n = _n;
tree.resize(4*n+5);
lazy.resize(4*n+5);
}
void prop(int node,int l,int r){
if(lazy[node].second) tree[node] = 0;
tree[node] += (r - l + 1) * lazy[node].first;
if(l != r){
lazy[node<<1].first += lazy[node].first;
lazy[node<<1|1].first += lazy[node].first;
lazy[node<<1].second |= lazy[node].second;
lazy[node<<1|1].second |= lazy[node].second;
}
lazy[node] = {0,0};
}
void update(int node,int l,int r,int lQ,int rQ,int val){
if(l>r) return;
if(lazy[node].first || lazy[node].second) prop(node,l,r);
if(lQ>r || l>rQ) return;
if(lQ<=l&&r<=rQ) return lazy[node].first += val, prop(node,l,r), void();
int md = l + r >> 1;
update(node<<1,l,md,lQ,rQ,val), update(node<<1|1,md+1,r,lQ,rQ,val);
tree[node] = tree[node<<1] + tree[node<<1|1];
}
void clear(){
if(lazy[1].first || lazy[1].second) prop(1,1,n);
lazy[1] = {0,1}, prop(1,1,n);
}
void update(int l,int r,int val=1){
update(1,1,n,l,r,val);
}
int query(int node,int l,int r,int lQ,int rQ){
if(l>r) return 0;
if(lazy[node].first || lazy[node].second) prop(node,l,r);
if(lQ>r || l>rQ) return 0;
if(lQ<=l&&r<=rQ) return tree[node];
int md = l + r >> 1;
return query(node<<1,l,md,lQ,rQ) + query(node<<1|1,md+1,r,lQ,rQ);
}
int query(int l,int r){
return query(1,1,n,l,r);
}
};
void solve(){
int n;
cin>>n;
vector<pair<int,int>> v(n);
for(auto &[l,r] : v) cin>>l>>r;
int q;
cin>>q>>q>>q;
vector<int> tmp;
for(auto [l,r] : v) tmp.push_back(l);
for(auto [l,r] : v) tmp.push_back(r);
compress(tmp);
for(int i=0;i<n;i++) v[i] = {tmp[i],tmp[i+n]};
assert(*max_element(tmp.begin(),tmp.end())<=2*n);
segTree sg(2*n);
int ans = 1;
for(auto [l,r] : v){
if(sg.query(l,r)) {
sg.clear();
ans ++;
}
sg.update(l,r);
}
cout<<ans<<endl;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t=1;
//cin>>t;
while(t--){
solve();
}
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
Main.cpp: In member function 'void segTree::update(int, int, int, int, int, int)':
Main.cpp:47:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
47 | int md = l + r >> 1;
| ~~^~~
Main.cpp: In member function 'int segTree::query(int, int, int, int, int)':
Main.cpp:63:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
63 | int md = l + r >> 1;
| ~~^~~
Main.cpp: In function 'void solve()':
Main.cpp:74:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
74 | for(auto &[l,r] : v) cin>>l>>r;
| ^
Main.cpp:78:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
78 | for(auto [l,r] : v) tmp.push_back(l);
| ^
Main.cpp:79:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
79 | for(auto [l,r] : v) tmp.push_back(r);
| ^
Main.cpp:85:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
85 | for(auto [l,r] : v){
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |