#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int q;
int queryType[500002], queryS[500002], queryE[500002];
multiset<pair<int, int> > st;
multiset<int> mst;
namespace case1{
multiset<pair<int, int> > setL;
multiset<pair<int, int> > setR;
void addCase1(pair<int, int> p){
setL.insert({-p.first, p.second});
setR.insert({p.second, -p.first});
}
void deleteCase1(pair<int, int> p){
setL.erase(setL.find({-p.first, p.second}));
setR.erase(setR.find({p.second, -p.first}));
}
bool existCase1(){
return (-setL.begin()->first) < (setR.begin()->first);
}
int getCase1(){
return setL.begin()->second + setR.begin()->second;
}
}
namespace case2{
int k;
int segTreeLoc[500002];
vector<pair<int, int> > v;
int tree[2000002], lazy[2000002];
void initialize(int i, int l, int r){
if(l==r){
tree[i] = 2e8;
lazy[i] = 0;
return;
}
int m = (l+r)>>1;
initialize(i*2, l, m);
initialize(i*2+1, m+1, r);
tree[i] = min(tree[i*2], tree[i*2+1]);
}
void renumber(){
v.clear();
for(int i=1; i<=q; i++){
if(queryType[i] == -1) continue;
v.push_back({queryE[i], i});
}
sort(v.begin(), v.end());
k = (int)v.size();
for(int i=0; i<k; i++){
segTreeLoc[v[i].second] = i+1;
}
map<pair<int, int>, vector<int> > mp;
for(int i=1; i<=q; i++){
if(queryType[i] == 1) mp[{queryS[i], queryE[i]}].push_back(i);
else{
segTreeLoc[i] = segTreeLoc[mp[{queryS[i], queryE[i]}].back()];
mp[{queryS[i], queryE[i]}].pop_back();
}
}
initialize(1, 1, k);
}
void propagate(int i, int l, int r){
if(l!=r) lazy[i*2] += lazy[i], lazy[i*2+1] += lazy[i];
tree[i] += lazy[i];
lazy[i] = 0;
return;
}
void addValue(int i, int l, int r, int s, int e, ll val){
propagate(i, l, r);
if(r<s || l>e) return;
if(s<=l && r<=e){
lazy[i] += val;
propagate(i, l, r);
return;
}
int m = (l+r)>>1;
addValue(i*2, l, m, s, e, val); addValue(i*2+1, m+1, r, s, e, val);
tree[i] = min(tree[i*2], tree[i*2+1]);
}
void addCase2(int i){
addValue(1, 1, k, segTreeLoc[i], segTreeLoc[i], -1e8-queryS[i]); /// ������ ���� ��ġ�� ����Ʈ Ʈ���� �ݿ��Ѵ�.
int tmp = lower_bound(v.begin(), v.end(), make_pair(queryS[i], INT_MAX)) - v.begin();
if(tmp) addValue(1, 1, k, 1, tmp, -1e8+queryE[i]);
}
void deleteCase2(int i){
addValue(1, 1, k, segTreeLoc[i], segTreeLoc[i], 1e8+queryS[i]); /// ������ ���� ��ġ�� ����Ʈ Ʈ���� �ݿ��Ѵ�.
int tmp = lower_bound(v.begin(), v.end(), make_pair(queryS[i], INT_MAX)) - v.begin();
if(tmp) addValue(1, 1, k, 1, tmp, 1e8-queryE[i]);
}
int getCase2(){
propagate(1, 1, k);
return tree[1];
}
}
int main(){
scanf("%d", &q);
for(int i=1; i<=q; i++){
char c;
scanf(" %c %d %d", &c, &queryS[i], &queryE[i]);
if(c=='A') queryType[i] = 1;
else queryType[i] = -1;
}
case2::renumber();
for(int i=1; i<=q; i++){
if(queryType[i] == 1){
int s = queryS[i], e = queryE[i];
st.insert({s, e});
case1::addCase1({s, e});
case2::addCase2(i);
}
else{
int s = queryS[i], e = queryE[i];
st.erase(st.find({s, e}));
case1::deleteCase1({s, e});
case2::deleteCase2(i);
}
if(st.size() == 1) printf("%d\n", st.begin()->second - st.begin()->first);
else if(case1::existCase1()) printf("%d\n", case1::getCase1());
else printf("%d\n", case2::getCase2());
}
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:118:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
118 | scanf("%d", &q);
| ~~~~~^~~~~~~~~~
Main.cpp:121:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
121 | scanf(" %c %d %d", &c, &queryS[i], &queryE[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
526 ms |
42948 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |