제출 #293687

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
293687		crossing0ver	Interval Collection (CCO20_day2problem2)	C++17	0 / 25	77 ms	55292 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);
}

int L[2][10000000],R[2][1000000],A[2][1000000],id[2]={1,1};
int PX,PY,C[2][1000000];


// x >= PX, y-minimal

int get_y(int vy,int tl,int tr) {
    if (!vy || !A[vy]) return inf;
    if (tl == tr) {
        if (A[0][vy]) return tl;
        return inf;
    }
    int tm = (tl + tr)/2;
    int a = get_y(L[0][vy],tl,tm);
    if (a != inf) return a;
    return get_y(R[0][vy],tm+1,tr);
   // return max( get_y(L[vy],tl,tm), get_y(R[vy]))
}
int get_x(int vx,int tlx,int trx) {
    if (trx < PX || !vx) return inf;
    if (tlx >= PX) {
            if (C[0][vx])
        return get_y(C[0][vx],1,1e6);
        else return inf;
    }
    int tmx = (tlx + trx)/2;
    int a = inf,b = inf;
    if (L[0][vx]) a = get_x(L[0][vx],tlx,tmx);
    if (R[0][vx]) b = get_x(R[0][vx],tmx+1,trx);
    return min(a,b);
}
void upd_y(int vy,bool flag,int tl,int tr,int val,int a,int b) {
   // if (tr < PY || tl > PY) return;
    if (tl == tr) {
        if (flag)
            A[0][vy]+=val;
        else A[0][vy] = A[0][a] + A[0][b];
        return;
    }
        else {
            int tm = (tl + tr)/2;
            if (tl <= tm) {
                    if (!L[0][vy]) L[0][vy] = ++id[0];
                upd_y(L[0][vy],flag,tl,tm,val,L[0][a],L[0][b]);
            }else {
                    if (!R[0][vy]) R[0][vy] = ++id[0];
                upd_y(R[0][vy],flag,tm+1,tr,val,R[0][a],R[0][b]);
            }
        }
    A[0][vy] = A[0][L[0][vy]] + A[0][R[0][vy]];
}
void upd_x(int vx,int tlx,int trx,int val) {
   // if (PX > trx || PX < tlx) return;
    if (tlx < trx) {
        int tmx = (tlx + trx)/2;
        if (PX <= tmx) {
        if (!L[0][vx]) L[0][vx] = ++id[0];
        upd_x(L[0][vx],tlx,tmx,val);
        }else {
        if (!R[0][vx]) R[0][vx] = ++id[0];
        upd_x(R[0][vx],tmx+1,trx,val);
        }
    }
    if (!C[0][vx]) C[0][vx] = ++id[0];
    upd_y(C[0][vx],tlx == trx,1,1e6,val,C[0][L[0][vx]],C[0][R[0][vx]]);
}


// x <= PX, y max
int GET_Y(int vy,int tl,int tr) {
    if (!vy || !A[vy]) return -inf;
    if (tl == tr) {
        if (A[1][vy]) return tl;
        return -inf;
    }
    int tm = (tl + tr)/2;
    int a = GET_Y(R[1][vy],tm+1,tr);
    if (a != -inf) return a;
    return GET_Y(L[1][vy],tl,tm);
   // return max( get_y(L[vy],tl,tm), get_y(R[vy]))
}
int GET_X(int vx,int tlx,int trx) {
    if (tlx > PX || !vx) return -inf;
    if (trx <= PX) {
            if (C[1][vx])
        return GET_Y(C[1][vx],1,1e6);
        else return -inf;
    }
    int tmx = (tlx + trx)/2;
    int a = -inf,b = -inf;
    if (L[1][vx]) a = GET_X(L[1][vx],tlx,tmx);
    if (R[1][vx]) b = GET_X(R[1][vx],tmx+1,trx);
    return max(a,b);
}
void UPD_Y(int vy,bool flag,int tl,int tr,int val,int a,int b) {
   // if (tr < PY || tl > PY) return;
    if (tl == tr) {
        if (flag)
            A[1][vy]+=val;
        else A[1][vy] = A[1][a] + A[1][b];
        return;
    }
        else {
            int tm = (tl + tr)/2;
            if (tl <= tm) {
                    if (!L[1][vy]) L[1][vy] = ++id[1];
                UPD_Y(L[1][vy],flag,tl,tm,val,L[1][a],L[1][b]);
            }else {
                    if (!R[1][vy]) R[1][vy] = ++id[1];
                UPD_Y(R[1][vy],flag,tm+1,tr,val,R[1][a],R[1][b]);
            }
        }
    A[1][vy] = A[1][L[1][vy]] + A[1][R[1][vy]];
}
void UPD_X(int vx,int tlx,int trx,int val) {
    //cout <<"OG";
   // if (PX > trx || PX < tlx) return;
    if (tlx < trx) {
        int tmx = (tlx + trx)/2;
        if (PX <= tmx) {
        if (!L[1][vx]) L[1][vx] = ++id[1];
        UPD_X(L[1][vx],tlx,tmx,val);
        }else {
        if (!R[1][vx]) R[1][vx] = ++id[1];
        UPD_X(R[1][vx],tmx+1,trx,val);
        }
    }
    if (!C[1][vx]) C[1][vx] = ++id[1];
    UPD_Y(C[1][vx],tlx == trx,1,1e6,val,C[1][L[1][vx]],C[1][R[1][vx]]);
}
int cans=INT_MAX;


int t[2][4*N],timer;
int *H[100000000];
int val[10000000];
void change(int&x,int c) {
    ++timer;
    H[timer] = &x;
    val[timer] = x;
    x = c;
}
void rollback() {
    (*H[timer]) = val[timer];
    timer--;
}
void add(int v,int tl,int tr,int pos,int val,int type) {
    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,pos,val,type);
    }
    else add(v*2+1,tm+1,tr,pos,val,type);
    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 get(int v,int tl,int tr,int l,int r,int type) {
    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,l,r,type),get(v*2+1,tm+1,tr,l,r,type));
    else return max(get(v*2,tl,tm,l,r,type),get(v*2+1,tm+1,tr,l,r,type));
}

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;
        PX = r;
     //   PY = r;

        cans = min(cans, -l + get(1,1,1e6,r,1e6,0));
        PX = l;
        cans = min(cans, r - get(1,1,1e6,1,l,1));
        PX = l;
        PY = r;
        add(1,1,1e6,l,r,0); // l-ze patara r-ebshi udidesi l, r-ze did l-ebshi umciresi r
        add(1,1,1e6,r,l,1);
        PX = r;
        PY = l;
      //  UPD_X(1,1,1e6,1);
    }
    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;//,cout << cans <<'s'<<'\n';

    }
    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() {
    int q;
    cin >> q;
    multiset<int> L,R;
    multiset<int> AL[1004],AR[1004];
    map<pii,vector<int> > cnt;
    for (int i = 1; i < 4*1000000;i ++)
        t[0][i] = inf, t[1][i] = -inf;
    for (int i = 1; i <= q; i++) {
        char c;
        int l,r;
        cin >> c >> l >> r;
        if (c == 'A') {
                cnt[{l,r}].pb(i);
            L.insert(l);
            R.insert(r);
            AR[l].insert(r);
            AL[r].insert(l);
        }else {
            qer(1,1,q,cnt[{l,r}].back(),i-1,l,r);
            cnt[{l,r}].pop_back();
            if (cnt[{l,r}].empty())
                cnt.erase({l,r});
           // query.push_back({cnt[{l,r}].back(),i})
            AL[r].erase(AL[r].find(l));
            AR[l].erase(AR[l].find(r));
          //  AL[r].erase(find(all(AL[r]),l));
          //  AR[l].erase(find(all(AR[l]),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;
       // cout << r - l <<'\n';
        }else {
            F[i] = 1;
        }}
        for (auto&i : cnt) {
            for (int j : i.second)
                qer(1,1,q,j,q,i.fi.fi,i.fi.se);
        }
        dfs(1,1,q);
        for (int i = 1; i <= q; i++)
            cout << ANS[i] <<'\n';

}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp:257:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  257 | main() {
      |      ^

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