oj.uz

Submission #892522

# Submission time Handle Problem Language Result Execution time Memory
892522 2023-12-25T13:07:05 Z 1075508020060209tc Interval Collection (CCO20_day2problem2) C++14
4 / 25
 714 ms 87636 KB 
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define X first
#define Y second
int Q;
map<pair<int,int>,int>freqseg;
multiset<int>mstv;
map<int,int>mp;

void add(int l,int r){
if(freqseg.size()==1){
    mp[r]=l;
    return;
}
auto it=mp.lower_bound(r);

if(it==mp.begin()){
    mstv.insert((*it).first-l);
    mp[r]=l;
    return;
}
if(it==mp.end()){
    it=prev(it);
    mstv.insert(r-(*it).second);
    mp[r]=l;
    return;
}
int l1=(*it).second;int l2=(*prev(it)).second;
int r1=(*it).first;int r2=(*prev(it)).first;
mstv.erase(mstv.find(r1-l2));
mstv.insert(r1-l);
mstv.insert(r-l2);
mp[r]=l;
}

void del(int l,int r){
auto it=mp.lower_bound(r);

if(it==mp.begin()){
    mstv.erase(mstv.find((*next(it)).first-l));
    mp.erase(r);
    return;
}
if(next(it)==mp.end()){
    mstv.erase(mstv.find(r-(*prev(it)).second));
    mp.erase(r);
    return;
}
int l2=(*next(it)).second;int l1=(*prev(it)).second;
int r2=(*next(it)).first;int r1=(*prev(it)).first;
mstv.insert(r2-l1);
mp.erase(r);
mstv.erase(mstv.find(r2-l));
mstv.erase(mstv.find(r-l1));
}

signed main(){
cin.tie(0);
ios_base::sync_with_stdio(0);
cin>>Q;
while(Q--){
    char typ;
    cin>>typ;
    int l;int r;
    cin>>l>>r;
    if(typ=='A'){
        freqseg[{l,r}]++;
        if(freqseg[{l,r}]==1){
            add(l,r);
        }
    }else{
        freqseg[{l,r}]--;
        if(freqseg[{l,r}]==0){
            del(l,r);
            freqseg.erase({l,r});
        }
    }
    if(freqseg.size()==1){
        int l=(*freqseg.begin()).first.first;
        int r=(*freqseg.begin()).first.second;
        cout<<r-l<<"\n";
    }else{
        cout<<(*mstv.begin())<<"\n";
    }
}



}

Compilation message

Main.cpp: In function 'void add(long long int, long long int)':
Main.cpp:30:5: warning: unused variable 'l1' [-Wunused-variable]
   30 | int l1=(*it).second;int l2=(*prev(it)).second;
      |     ^~
Main.cpp:31:24: warning: unused variable 'r2' [-Wunused-variable]
   31 | int r1=(*it).first;int r2=(*prev(it)).first;
      |                        ^~
Main.cpp: In function 'void del(long long int, long long int)':
Main.cpp:51:5: warning: unused variable 'l2' [-Wunused-variable]
   51 | int l2=(*next(it)).second;int l1=(*prev(it)).second;
      |     ^~
Main.cpp:52:30: warning: unused variable 'r1' [-Wunused-variable]
   52 | int r2=(*next(it)).first;int r1=(*prev(it)).first;
      |                              ^~

Subtask #1
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 35156 KB Output is correct
2 Correct 183 ms 35128 KB Output is correct
3 Correct 387 ms 70228 KB Output is correct
4 Correct 430 ms 70040 KB Output is correct
5 Correct 505 ms 87636 KB Output is correct
6 Correct 481 ms 87496 KB Output is correct
7 Correct 681 ms 10904 KB Output is correct
8 Correct 502 ms 8016 KB Output is correct
9 Correct 465 ms 7764 KB Output is correct
10 Correct 710 ms 13704 KB Output is correct
11 Correct 503 ms 8140 KB Output is correct
12 Correct 459 ms 7724 KB Output is correct
13 Correct 714 ms 14996 KB Output is correct
14 Correct 497 ms 8272 KB Output is correct
15 Correct 472 ms 7708 KB Output is correct
16 Correct 293 ms 9044 KB Output is correct
17 Correct 295 ms 9044 KB Output is correct
18 Correct 305 ms 8788 KB Output is correct
19 Correct 303 ms 9040 KB Output is correct
20 Correct 292 ms 8784 KB Output is correct

Subtask #5
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -