#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], result[2000002], pqtop[2000002];
bool erased[500002];
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq[2000002];
void initialize(int i, int l, int r){
pq[i].push(make_pair(1e8, 0));
pqtop[i] = 1e8;
if(l==r){
tree[i] = 1e8;
lazy[i] = 0;
result[i] = 2e8;
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]);
result[i] = min({result[i*2], result[i*2+1], tree[i] + pqtop[i]});
}
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];
else tree[i] += lazy[i];
result[i] += lazy[i];
lazy[i] = 0;
return;
}
void addValue(int i, int l, int r, int s, int e, int 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]);
result[i] = min({result[i*2], result[i*2+1], tree[i] + pqtop[i]});
}
void addKey(int i, int l, int r, int s, int e, pair<int, int> p){
propagate(i, l, r);
if(r<s || l>e) return;
if(s<=l && r<=e){
pq[i].push(p);
pqtop[i] = pq[i].top().first;
result[i] = pqtop[i] + tree[i];
return;
}
int m = (l+r)>>1;
addKey(i*2, l, m, s, e, p); addKey(i*2+1, m+1, r, s, e, p);
tree[i] = min(tree[i*2], tree[i*2+1]);
result[i] = min({result[i*2], result[i*2+1], tree[i] + pqtop[i]});
}
void removeKey(int i, int l, int r, int s, int e){
if(r<s || l>e) return;
if(s<=l && r<=e){
while(erased[pq[i].top().second]) pq[i].pop();
pqtop[i] = pq[i].top().first;
result[i] = pqtop[i] + tree[i];
return;
}
int m = (l+r)>>1;
removeKey(i*2, l, m, s, e); removeKey(i*2+1, m+1, r, s, e);
tree[i] = min(tree[i*2], tree[i*2+1]);
result[i] = min({result[i*2], result[i*2+1], tree[i] + pqtop[i]});
}
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) addKey(1, 1, k, 1, tmp, {queryE[i], i});
}
void deleteCase2(int i){
erased[segTreeLoc[i]] = 1;
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) removeKey(1, 1, k, 1, tmp);
}
int getCase2(){
propagate(1, 1, k);
return result[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:156:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
156 | scanf("%d", &q);
| ~~~~~^~~~~~~~~~
Main.cpp:159:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
159 | scanf(" %c %d %d", &c, &queryS[i], &queryE[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
63104 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
63104 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
63104 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
705 ms |
132964 KB |
Output is correct |
| 2 |
Correct |
734 ms |
134116 KB |
Output is correct |
| 3 |
Correct |
1530 ms |
204336 KB |
Output is correct |
| 4 |
Correct |
1536 ms |
207032 KB |
Output is correct |
| 5 |
Correct |
1758 ms |
232412 KB |
Output is correct |
| 6 |
Correct |
1918 ms |
236880 KB |
Output is correct |
| 7 |
Incorrect |
3791 ms |
122252 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
63104 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
