이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include"bits/stdc++.h"
using namespace std;
#define MP(a,b) make_pair(a,b)
//RAQ RMQ セグメント木
struct SegmentTree{
private:
int n;
vector<long long> nodes,lazy;
public:
void init(int N){ //初期化する O(N)
nodes.clear();
lazy.clear();
n = 1;
while(n < N) n *= 2;
n = 2 * n -1;
for(int i=0; i<n; i++){
nodes.push_back(0);
lazy.push_back(0);
}
}
void eval(int k, int l, int r){ //遅延評価を行う
if(lazy[k] == 0) return;
nodes[k] += lazy[k];
if(r-l > 1){
lazy[2*k+1] += lazy[k];
lazy[2*k+2] += lazy[k];
}
lazy[k] = 0;
}
void add(int a, int b, long long x, int k=0, int l=0, int r=-1){ //区間に対して値を加算する O(log N)
if(r == -1) r = n/2+1;
eval(k, l, r);
if(r <= a || b <= l) return; //交差する場合
if(a <= l && r <= b){ //完全に含む場合
lazy[k] += x;
eval(k, l, r);
}
else{
add(a, b, x, 2*k+1, l, (l+r)/2);
add(a, b, x, 2*k+2, (l+r)/2, r);
nodes[k] = min(nodes[2*k+1], nodes[2*k+2]);
}
}
long long minimum(int a, int b, int k=0, int l=0, int r=-1){ //[a,b)の最小値を求める O(log N)
//cout << a << " " << b << " " << k << " " << l << " " << r << endl;
if(r == -1) r = n/2+1;
if(r <= a || b <= l) return LLONG_MAX; //交差する場合
eval(k, l, r);
if(a <= l && r <= b) return nodes[k]; //完全に含む場合
long long valueL = minimum(a, b, k*2+1, l, (l+r)/2);
long long valueR = minimum(a, b, k*2+2, (l+r)/2, r);
return min(valueL, valueR);
}
void print(){
cout << "nodes" << endl;
int sp = n;
int nx = 0;
for(int i=0; i<nodes.size(); i++){
cout << nodes[i];
for(int j=0; j<sp; j++) cout << " ";
if(i == nx){
nx = nx*2+2;
sp /= 2;
cout << endl;
}
}
cout << "lazy" << endl;
sp = n;
nx = 0;
for(int i=0; i<lazy.size(); i++){
cout << lazy[i];
for(int j=0; j<sp; j++) cout << " ";
if(i == nx){
nx = nx*2+2;
sp /= 2;
cout << endl;
}
}
cout << endl;
}
};
int N;
int A[200000],B[200000],C[200000],D[200000];
set<pair<int,int>> nokori[200000];
bool already1[200000] = {};
bool already2[200000] = {};
vector<int> all,diff;
SegmentTree st;
int main(){
scanf("%d", &N);
for(int i=0; i<N; i++){
scanf("%d%d", A+i, B+i);
A[i]--;
all.push_back(B[i]);
nokori[A[i]].insert(MP(B[i],i));
}
for(int i=0; i<N; i++){
scanf("%d%d", C+i, D+i);
C[i]--;
all.push_back(D[i]);
}
sort(all.begin(), all.end());
//
vector<int> moto,ato;
for(int i=N-1; i>=0; i--){
if(!already1[i]) moto.push_back(B[i]);
}
for(int i=N-1; i>=0; i--){
if(!already2[i]) ato.push_back(D[i]);
}
int idx1 = 0;
int idx2 = 0;
for(int i=0; i<all.size(); i++){
while(idx1 < moto.size() && moto[idx1] <= all[i]) idx1++;
while(idx2 < ato.size() && ato[idx2] <= all[i]) idx2++;
diff.push_back(idx1-idx2);
}
st.init(all.size());
for(int i=0; i<all.size(); i++) st.add(i, i+1, diff[i]);
//
int ans = N;
for(int i=N-1; i>=0; i--){
auto itr = nokori[C[i]].upper_bound(MP(D[i]+1, -1));
int tmp;
if(itr == nokori[C[i]].begin()) tmp = -1;
else{
itr--;
tmp = itr->second;
nokori[C[i]].erase(itr);
already1[tmp] = false;
already2[i] = false;
st.add(lower_bound(all.begin(), all.end(), B[tmp])-all.begin(), all.size(), -1);
st.add(lower_bound(all.begin(), all.end(), D[i])-all.begin(), all.size(), +1);
}
if(st.minimum(0,all.size()) >= 0 && tmp >= 0){
ans--;
}
else{
if(tmp >= 0){
nokori[C[i]].insert(MP(B[tmp],tmp));
already1[tmp] = false;
already2[i] = false;
st.add(lower_bound(all.begin(), all.end(), B[tmp])-all.begin(), all.size(), +1);
st.add(lower_bound(all.begin(), all.end(), D[i])-all.begin(), all.size(), -1);
}
}
}
printf("%d\n", ans);
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
worst_reporter2.cpp: In member function 'void SegmentTree::print()':
worst_reporter2.cpp:59:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<nodes.size(); i++){
~^~~~~~~~~~~~~
worst_reporter2.cpp:71:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<lazy.size(); i++){
~^~~~~~~~~~~~
worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:118:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<all.size(); i++){
~^~~~~~~~~~~
worst_reporter2.cpp:119:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(idx1 < moto.size() && moto[idx1] <= all[i]) idx1++;
~~~~~^~~~~~~~~~~~~
worst_reporter2.cpp:120:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(idx2 < ato.size() && ato[idx2] <= all[i]) idx2++;
~~~~~^~~~~~~~~~~~
worst_reporter2.cpp:125:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<all.size(); i++) st.add(i, i+1, diff[i]);
~^~~~~~~~~~~
worst_reporter2.cpp:93:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
worst_reporter2.cpp:95:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", A+i, B+i);
~~~~~^~~~~~~~~~~~~~~~~~
worst_reporter2.cpp:101:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", C+i, D+i);
~~~~~^~~~~~~~~~~~~~~~~~
# | 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... |