Submission #986279

#	Time	Username	Problem	Language	Result	Execution time	Memory
986279		vjudge1	Interval Collection (CCO20_day2problem2)	C++17	25 / 25	6453 ms	199712 KiB

Main

#pragma GCC optimize("Ofast,fast-math,unroll-loops")
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;
using ld = long double;

//#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

const int inf = 1e9 + 9;
const int nmax = 1e6 + 1;

template<typename T>
struct AINT {
   vector<T> aint;
   int n;
   void init(int n_) {
      n = n_;
      aint.resize(n * 2 + 5, T());
   }
   template<class CB> void walk(CB&& cb) { walk(cb, 1, n); }
   template<class CB> void walk(CB&& cb, int l, int r) { walk(cb, l, r, 1, 1, n); }
   template<class CB> void walk(CB&& cb, int l, int r, int node, int cl, int cr) { 
      if(cr < l || r < cl) return;
      if(l <= cl && cr <= r && !cb(aint[node], cl, cr)) return;
      int mid = (cl + cr) >> 1, L = node + 1, R = node + (mid - cl + 1) * 2;
      walk(cb, l, r, L, cl, mid);
      walk(cb, l, r, R, mid + 1, cr);
      aint[node].pull(aint[L], aint[R]);
   }
};

namespace DS {
   auto byL = [](pii a, pii b) { return a.first < b.first || (a.first == b.first && a.second > b.second); };
   auto byR = [](pii a, pii b) { return a.second < b.second || (a.second == b.second && a.first > b.first); };
   
   struct segm {
      int l, r;
      segm(): l(-inf * 2), r(inf * 2) {;}
      void pull(const segm& a, const segm& b) { l = max(a.l, b.l); r = min(b.r, a.r); }
   };
   
   AINT<segm> aint;
   vector<int> ans;
   vector<pair<int, segm>> rollback;
   vector<pii> sortL, sortR;
   
   void insert(int l, int r) {
      sortL.emplace_back(sortL.empty()? pii{l, r} : byL(sortL.back(), pii{l, r})? pii{l, r} : sortL.back());
      sortR.emplace_back(sortR.empty()? pii{l, r} : !byR(sortR.back(), pii{l, r})? pii{l, r} : sortR.back());
      sortL.emplace_back(sortL.back());
      sortR.emplace_back(sortR.back());
      
      ans.push_back(ans.empty()? inf : ans.back());
      aint.walk([&](segm& val, int cl, int cr) {
         ans.back() = min(ans.back(), r - val.l); return 0;
      }, 1, l);
      aint.walk([&](segm& val, int cl, int cr) {
         ans.back() = min(ans.back(), val.r - l); return 0;
      }, r, nmax);
      
      aint.walk([&](segm& val, int cl, int cr) {
         rollback.emplace_back(cl, val);
         val.r = min(val.r, r);
         return 0;
      }, l, l);
      aint.walk([&](segm& val, int cl, int cr) {
         rollback.emplace_back(cl, val);
         ans.emplace_back(ans.back());
         val.l = max(val.l, l);
         return 0;
      }, r, r);
      
      assert(ans.size() == rollback.size());
   }
   
   int time() { return sz(rollback); }
   void pop() {
      aint.walk([&](segm& val, int cl, int cr) {
         val = rollback.back().second;
         return 0;
      }, rollback.back().first, rollback.back().first);
      
      ans.pop_back();
      sortL.pop_back();
      sortR.pop_back();
      rollback.pop_back();
   }
   
   int query() {
      
      //for(auto [a, b] : sortL) cerr << a << ' ' << b << '\t';
      //cerr << "--\n";
      
      if(ans.empty() || ans.back() >= nmax + 5) {
         auto a = sortL.back(), b = sortR.back();
         return max(b.second, a.second) - min(b.first, a.first);
      }
      return ans.back();
   }
}


int started = 0;

struct memory {
   vector<pii> values;
   int enter_time;
   void pull(const memory& a, const memory& b) {
      if(!started) return;
      while(DS::time() > enter_time) DS::pop();
   }
};

signed main() {
   cin.tie(0) -> sync_with_stdio(0);
   int n;
   cin >> n;
   
   map<pii, vector<int>> still;
   vector<pii> segms;
   vector<pii> times;
   for(int i = 1; i <= n; i++) {
      char ch;
      cin >> ch;
      if(ch == 'A') {
         int l, r;
         cin >> l >> r;
         segms.emplace_back(l, r);
         times.emplace_back(i, n);
         still[pii{l, r}].emplace_back(sz(segms) - 1);
      }
      else {
         int l, r;
         cin >> l >> r;
         auto t = still[pii{l, r}].back();
         still[pii{l, r}].pop_back();
         times[t].second = i - 1;
      }
   }
   
   
   AINT<memory> foroper;
   foroper.init(n);
   
   DS::aint.init(nmax);
   DS::sortL.reserve(nmax);
   DS::ans.reserve(nmax);
   DS::rollback.reserve(nmax);
   DS::sortR.reserve(nmax);
   
   for(int i = 0; i < sz(segms); i++) {
      foroper.walk([&](memory& val, int cl, int cr) {
         val.values.emplace_back(segms[i]);
         return 0;
      }, times[i].first, times[i].second);
   }
   
   started = 1;
   foroper.walk([&](memory& val, int cl, int cr) {
      val.enter_time = DS::time();
      for(auto [a, b] : val.values) DS::insert(a, b);
      
      if(cl != cr) return 1;
      cout << DS::query() << '\n';
      
      while(DS::time() > val.enter_time) DS::pop();
      return 0;
   });
   
   return 0;
}

/**
      Istenem! Nu poate fi real.
-- Surse verificate
*/

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