Submission #293727

#	Time	Username	Problem	Language	Result	Execution time	Memory
293727		crossing0ver	Interval Collection (CCO20_day2problem2)	C++17	18 / 25	6617 ms	653980 KiB

Main

#include<bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define fi first
#define se second
#define pb push_back
using namespace std;
const int N = 1e6+6,inf = 1e8;
int F[N],ANS[N];
vector<pii> Q[N];
void qer(int v,int tl,int tr,int l,int r,int QL,int QR) {
    if (l > tr || r < tl) return;
    if (l <= tl && r  >= tr) {
        Q[v].pb({QL,QR});
        return;
    }
    int tm = (tl + tr)/2;
    qer(v*2,tl,tm,l,r,QL,QR);
    qer(v*2+1,tm+1,tr,l,r,QL,QR);
}



// x >= PX, y-minimal



// x <= PX, y max
int cans=INT_MAX;
int t[2][4*N],timer;
int *H[130000000];
int val[130000000];
void change(int&x,int c) {
    ++timer;
    H[timer] = &x;
    val[timer] = x;
    x = c;
}
void rollback() {
    (*H[timer]) = val[timer];
    timer--;
}
bool type;
int VAL,pos;
void add(int v,int tl,int tr) {
    if (tl == tr) {
        if (type == 0)
            change(t[0][v],min(t[0][v],VAL));
        else change(t[1][v],max(t[1][v],VAL));
       // t[0][v] += val;
        return;
    }
    int tm = (tl + tr)/2;
    if (pos <= tm) {
    add(v*2,tl,tm);
    }
    else add(v*2+1,tm+1,tr);
    if (type == 0)
        change(t[0][v],min(t[0][v*2],t[0][v*2+1]));
    else
         change(t[1][v],max(t[1][v*2],t[1][v*2+1]));
    //t[v] = t[v*2] + t[v*2+1];
}
int L,R;
int get(int v,int tl,int tr) {
    if (L> tr || R < tl) {
        if (type == 0) return inf;
        else return -inf;
    }
    if (L <= tl && R >= tr) return t[type][v];
    int tm = (tl + tr)/2;
    if (type == 0)
        return min(get(v*2,tl,tm),get(v*2+1,tm+1,tr));
    else return max(get(v*2,tl,tm),get(v*2+1,tm+1,tr));
}

void dfs(int v,int tl,int tr) {
    int in_ans = cans;
    int start_time = timer;
    if (timer > 60000000) {
        while(true) {

        }
    }
    for (auto i1 : Q[v]) {
        int l = i1.fi;
        int r = i1.se;

        type = 0;
        L = r;
        R = 1e6;
        type = 0;
        if (cans > r - l)
        cans = min(cans, -l + get(1,1,1e6));
        L = 1;
        R = l;type = 1;
        if (cans > r - l)
        cans = min(cans, r - get(1,1,1e6));
        pos = l;
        VAL = r;
        type = 0;
        add(1,1,1e6); // l-ze patara r-ebshi udidesi l, r-ze did l-ebshi umciresi r
        pos = r;
        VAL = l;
        type = 1;
        add(1,1,1e6);
    }
    if (tl != tr) {
        int tm = (tl + tr)/2;
        dfs(v*2,tl,tm);
        dfs(v*2+1,tm+1,tr);
    }else {
        if (F[tl])
            ANS[tl] = cans;
    }
    while(start_time != timer) {
        rollback();
    }/*
    for (auto i1 : Q[v]) {
        int l = i1.fi;
        int r = i1.se;
       // PX = r;
     //   PY = r;

      //  cans = min(cans, -l + get_x(1,1,1e6);
      //  PX = l;
      //  cans = min(cans, r - GET_X(1,1,1e6));
        PX = l;
        PY = r;
        upd_x(1,1,1e6,-1); // l-ze patara r-ebshi udidesi l, r-ze did l-ebshi umciresi r
        PX = r;
        PY = l;
        UPD_X(1,1,1e6,-1);
    }*/
    cans = in_ans;






}
main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int q;
    cin >> q;
    multiset<int> L,R;
    multiset<int> AL[1000004],AR[1000004];
 //   map<pii,vector<int> > cnt;
    for (int i = 1; i < 4*1000000;i ++)
        t[0][i] = inf, t[1][i] = -inf;
    vector<pair<pii,char> > query(q+1);
    vector<pii> t(q);
    for (int i = 1; i <= q; i++) {
        char c;
        int l,r;
        cin >> c >> l >> r;
        query[i] = {{l,r},c};
        t[i-1] = {l,r};
    }
    sort(all(t));
    t.resize(unique(all(t)) - t.begin());
    map<pii,int> ID;
    for (int i = 0; i < t.size(); i++) {
        ID[t[i]] = i;
    }
    set<int> cnt[1000005];
    for (int i = 1; i <= q; i++) {
            char c=  query[i].se;
    int l = query[i].fi.fi;
    int r = query[i].fi.se;
    int id = ID[{l,r}];
        if (c == 'A') {
                cnt[id].insert(i);
            L.insert(l);
            R.insert(r);
            AR[l].insert(r);
            AL[r].insert(l);
        }else {
            qer(1,1,q,*cnt[id].begin(),i-1,l,r);
            cnt[id].erase(cnt[id].begin());
            AL[r].erase(AL[r].find(l));
            AR[l].erase(AR[l].find(r));
            L.erase(L.find(l));
            R.erase(R.find(r));
        }
        l = *L.rbegin();
        r = *R.begin();
        int len = max(0,r - l);
        if (len) {
        int l1 = l, r1 = r;
        r = *AR[l1].begin();
        l = *AL[r1].rbegin();
        ANS[i] = r-l;
        }else {
            F[i] = 1;
        }}
        for (int i= 0; i < t.size(); i++)
            for (int j : cnt[i])
                qer(1,1,q,j,q,t[i].fi,t[i].se);
        dfs(1,1,q);
        for (int i = 1; i <= q; i++)
            cout << ANS[i] <<'\n';
}

Compilation message (stderr)

Main.cpp:145:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  145 | main() {
      |      ^
Main.cpp: In function 'int main()':
Main.cpp:168:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  168 |     for (int i = 0; i < t.size(); i++) {
      |                     ~~^~~~~~~~~~
Main.cpp:202:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  202 |         for (int i= 0; i < t.size(); i++)
      |                        ~~^~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 8 / 8
• Subtask 3: 7 / 7
• Subtask 4: 0 / 4
• Subtask 5: 0 / 3