#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], 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;
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 addValue(int i, int l, int r, int idx, int val){
if(l==r){
tree[i] += val;
result[i] += val;
return;
}
int m = (l+r)>>1;
if(idx<=m) addValue(i*2, l, m, idx, val);
else addValue(i*2+1, m+1, r, idx, 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){
if(r<s || l>e) return;
if(s<=l && r<=e){
pq[i].push(p);
pqtop[i] = pq[i].top().first;
result[i] = tree[i] + pqtop[i];
if(l!=r) result[i] = min({result[i], result[i*2], result[i*2+1]});
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] = tree[i] + pqtop[i];
if(l!=r) result[i] = min({result[i], result[i*2], result[i*2+1]});
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], -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], 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(){
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:146:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
146 | scanf("%d", &q);
| ~~~~~^~~~~~~~~~
Main.cpp:149:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
149 | scanf(" %c %d %d", &c, &queryS[i], &queryE[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
52 ms |
63096 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
52 ms |
63096 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
52 ms |
63096 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
731 ms |
131184 KB |
Output is correct |
2 |
Correct |
708 ms |
132668 KB |
Output is correct |
3 |
Correct |
1379 ms |
201824 KB |
Output is correct |
4 |
Correct |
1428 ms |
204600 KB |
Output is correct |
5 |
Correct |
1677 ms |
229856 KB |
Output is correct |
6 |
Correct |
1861 ms |
234172 KB |
Output is correct |
7 |
Incorrect |
3609 ms |
122076 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
52 ms |
63096 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |