Submission #293952

#	Time	Username	Problem	Language	Result	Execution time	Memory
293952		crossing0ver	Interval Collection (CCO20_day2problem2)	C++17	0 / 25	1296 ms	317400 KiB

Main

#include<bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#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*4];
int l1,r1,QL,QR;
void qer(int v,int tl,int tr) {
    if (l1 > tr || r1 < tl) return;
    if (l1 <= tl && r1  >= tr) {
        Q[v].pb({QL,QR});
        return;
    }
    int tm = (tl + tr)/2;
    qer(v*2,tl,tm);
    qer(v*2+1,tm+1,tr);
}
int cans=INT_MAX;
int t[2][4*N],timer;
int *H[100000000];
int val[100000000];
void change(int&x,int c) {
    H[++timer] = &x;
    val[timer] = x;
    x = c;
}
void rollback() {
    (*H[timer--]) = val[timer];
}
bool type;
int VAL,pos,L,R;
int BIT[2][N];
const int REV = 1e6;
void add(int v=1,int tl=1,int tr=1e6) {
    if (tl == tr) {
        if (!type) {
            if (VAL < t[0][v])
            change(t[0][v],VAL);
        }
        else if  (VAL > t[1][v])
            change(t[1][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)
        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]));
}

void add1(int pos,int val,bool type) {
    if (type)
    for (;pos < 1e6; pos += pos&-pos)
        if (BIT[1][pos] < val)
            change(BIT[1][pos],val);
    else {
        for (;pos < 1e6; pos += pos&-pos)
        if (BIT[0][pos] > val)
            change(BIT[0][pos],val);
    }
}
int get1(int pos,bool type) {
    if (type == 0) {
        int s = inf;
    for (;pos;pos -= pos&-pos)
        s = min(s,BIT[0][REV - pos]);
        return s;
    }else {
            int s = -inf;
    for (;pos;pos -= pos&-pos)
        s = max(s,BIT[1][pos]);
        return s;
    }
}
int get(int v=1,int tl=1,int tr=1e6) {
    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)
        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));

}


int L1=-inf,R1=inf,AR1[N],AL1[N],HANS=inf;

void dfs(int v,int tl,int tr) {
    int in_ans = cans;
    int start_time = timer;
    for (auto& i1 : Q[v]) {
        int l = i1.fi;
        int r = i1.se;
        if (R1 > r)
            change(R1,r);
        if (L1 < l)
            change(L1,l);
        if (AR1[l] > r)
            change(AR1[l],r);
        if (AL1[r] < l)
            change(AL1[r],l);
        {
        int l2 = L1;
        int r2 = R1;
        int len = max(0,r2 - l2);
        if (len) {
        int r3 = AR1[l2];
        int l3 = AL1[r2];
        change(HANS,r3-l3);
        pos = l;
        VAL = r;
        type = 0;
        add1(REV - pos,VAL,0); // l-ze patara r-ebshi udidesi l, r-ze did l-ebshi umciresi r
        add();
        pos = r;
        VAL = l;
        type = 1;
        add1(pos,VAL,1);
        continue;
        }
        }
        L = r;
        R = 1e6;
        type = 0;
        if (cans > r - l) {
        cans = min(cans, -l + get1(REV - L,0));
        }
        L = 1;
        R = l;type = 1;
        if (cans > r - l)
        cans = min(cans, r - get1(R,1));
        pos = l;
        VAL = r;
        type = 0;
        add1(REV-pos,VAL,0); // l-ze patara r-ebshi udidesi l, r-ze did l-ebshi umciresi r
     //   add1(REV - pos,r,0);
     add();
        pos = r;
        VAL = l;
        type = 1;
        add1(pos,VAL,1);
       // add1(pos,VAL,1);
    }
    if (tl != tr) {
        int tm = (tl + tr)/2;
        dfs(v*2,tl,tm);
        dfs(v*2+1,tm+1,tr);
    }else {
                if (cans > 1000000)
                ANS[tl] = HANS;
        else
            ANS[tl] = cans;
    }
    while(start_time != timer)
        rollback();
    cans = in_ans;
}
main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int q;
    cin >> q;
    for (int i =  0; i < N; i++)
        AR1[i] = BIT[0][i] = inf,AL1[i] = BIT[1][i]=-inf;
    for (int i = 0; i < 4*N;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);
                else {
                        l1=*cnt[id].begin();
                        r1 = i-1;
                        QL= l;
                        QR = r;
            qer(1,1,q);
            cnt[id].erase(cnt[id].begin());
        }
            F[i] = 1;
        }
        for (int i= 0; i < t.size(); i++)
            for (int j : cnt[i]) {
                l1 = j;
                r1 = q;
                QL = t[i].fi;
                QR = t[i].se;
                qer(1,1,q);
            }
        dfs(1,1,q);
        for (int i = 1; i <= q; i++)
            cout << ANS[i] <<'\n';
}

Compilation message (stderr)

Main.cpp: In function 'void rollback()':
Main.cpp:38:14: warning: operation on 'timer' may be undefined [-Wsequence-point]
   38 |     (*H[timer--]) = val[timer];
      |         ~~~~~^~
Main.cpp:38:14: warning: operation on 'timer' may be undefined [-Wsequence-point]
Main.cpp: In function 'void add1(int, int, bool)':
Main.cpp:65:8: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   65 |     if (type)
      |        ^
Main.cpp: In function 'int get1(int, bool)':
Main.cpp:78:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   78 |     for (;pos;pos -= pos&-pos)
      |     ^~~
Main.cpp:80:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   80 |         return s;
      |         ^~~~~~
Main.cpp:83:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   83 |     for (;pos;pos -= pos&-pos)
      |     ^~~
Main.cpp:85:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   85 |         return s;
      |         ^~~~~~
Main.cpp: At global scope:
Main.cpp:174:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  174 | main() {
      |      ^
Main.cpp: In function 'int main()':
Main.cpp:196: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]
  196 |     for (int i = 0; i < t.size(); i++) {
      |                     ~~^~~~~~~~~~
Main.cpp:217: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]
  217 |         for (int i= 0; i < t.size(); i++)
      |                        ~~^~~~~~~~~~

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