Submission #528778

#	Time	Username	Problem	Language	Result	Execution time	Memory
528778		cadmiumsky	New Home (APIO18_new_home)	C++14	0 / 100	581 ms	59828 KiB

new_home

#include <bits/stdc++.h>

using namespace std;
const int nmax = 3e5 + 5;
const int ERROR = -1e9 - 7;
//#warning SA FACI K-URILE DE LA 1 LA K !!!
namespace {
  struct Shop {
    int x, c, a, b;
  }shop[nmax];
  struct Query {
    int l, y, rez = -1e9;
    void operator <<= (const int& x) {
      rez = (rez == ERROR? ERROR : max(rez, x));
    }
  } qs[nmax];
  int n, q, k;
  int ogn;
  int maxx = 0;
  namespace NORMALIZE { // de la 1
    map<int,int> normt;
    void normalize() {
      for(int i = 0; i < n; i++)
        normt[shop[i].a],normt[shop[i].b];
      for(int i = 0; i < q; i++)
        normt[qs[i].y];
      int cnt = 1;
      for(auto &x : normt)
        x.second = cnt++;
      for(int i = 0; i < n; i++)
        shop[i].a = normt[shop[i].a], shop[i].b = normt[shop[i].b];
      for(int i = 0; i < q; i++)
        qs[i].y = normt[qs[i].y];
      return;
    }
  }
  namespace INVALIDATE {
    vector<pair<int,int> > smen[nmax];
    void invalidate() {
      int temp = n;
      n = ogn;
      sort(shop, shop + n, [&](auto a, auto b) {return a.a < b.a;});
      for(int i = 0; i < n; i++) {
        if(smen[shop[i].c].size() == 0 || smen[shop[i].c].back().second < shop[i].a)
          smen[shop[i].c].push_back({shop[i].a, shop[i].b});
        else
          smen[shop[i].c].back().second = max(smen[shop[i].c].back().second, shop[i].b);
      }
      vector<int> events(NORMALIZE::normt.size() + 5);
      for(int i = 1; i <= k; i++) {
        for(auto [a, b] : smen[i])
          events[a]++, events[b + 1]--;
      }
      int l = 0;
      for(auto &x : events)
        x += l, l = x;
      for(int i = 0; i < q; i++) {
        if(events[qs[i].y] != k)
          qs[i].rez = ERROR;
      }
      n = temp;
      return;
    }
  }
  namespace READ {
    void read() {
      cin >> n >> k >> q;
      ogn = n;
      for(int i = 0; i < n; i++)
        cin >> shop[i].x >> shop[i].c >> shop[i].a >> shop[i].b, shop[i].x *= 2, maxx = max(maxx, shop[i].x);
      for(int i = 0;  i < q; i++)
        cin >> qs[i].l >> qs[i].y, qs[i].l *= 2, maxx = max(qs[i].l * 2, maxx);
      for(int i = 1; i <= k; i++)
        shop[n].x = 6e8, shop[n].c = i, shop[n].a = -1, shop[n].b = 1e8 + 1,
        n++,
        shop[n].x = -6e8, shop[n].c = i, shop[n].a = -1, shop[n].b = 1e8 + 1,
        n++,
        maxx = 6e8;
      return;
    }
  }
  namespace AINT {
    vector<int> tree;
    int len;
    void setup() {
      tree.resize((len = NORMALIZE::normt.size() + 1) * 4);
      fill(tree.begin(), tree.end(), -1e9);
    }
    void push(int l, int r, int val, int node = 1, int cl = 1, int cr = len) {
      if(r < l)
        return;
      if(r < cl || cr < l)
        return;
      if(l <= cl && cr <= r) {
        tree[node] = max(tree[node], val);
        return;
      }
      int mid = cl + cr >> 1;
      push(l, r, val, 2 * node, cl, mid);
      push(l, r, val, 2 * node + 1, mid + 1, cr);
    }
    int query(int poz, int node = 1, int cl = 1, int cr = len) {
      if(cl == cr)
        return tree[node];
      int mid = cl + cr >> 1;
      if(poz <= mid)
        return max(query(poz, 2 * node, cl, mid), tree[node]);
      return max(query(poz, 2 * node + 1, mid + 1, cr), tree[node]);
    }
  }
  struct Slope {
    int x0, xmax, a, b;
    bool operator < (const Slope& x) const {
      return xmax < x.xmax;
    }
  };
  namespace APPLY { // ai cout
    void apply(vector<Slope> slope) {
      ::AINT::setup();
      vector<pair<int,int> > events(slope.size() + q);
      int ptr = 0;
      for(int i = 0; i < slope.size(); i++)
        events[ptr++] = {0, i};
      for(int i = 0; i < q; i++)
        events[ptr++] = {1, i};
      auto getbypair = [&](pair<int,int> x) {
        if(x.first == 0)
          return slope[x.second].xmax;
        return qs[x.second].l;
      };
      sort(events.begin(), events.end(),
      [&](auto a, auto b) { return getbypair(a) < getbypair(b) 
                            || (getbypair(a) == getbypair(b) && a < b);});
      int type, i;
      for(auto ev : events) {
        tie(type, i) = ev;
        if(type == 0)
          AINT::push(slope[i].a, slope[i].b, slope[i].x0);
        else 
          qs[i] <<= AINT::query(qs[i].y) - qs[i].l;
      }
    }
  }
  namespace MAKESEGMENTS {
    unordered_map<int, Slope> mp;
    multiset<pair<int, int> > line[nmax];
    vector<Slope> slope;
    void erase(int poz, int time) {
      if(poz == -1)
        return;
      if(mp.find(poz) != mp.end()) {
        mp[poz].b = time - 1;
        slope.push_back(mp[poz]);
        mp.erase(poz);
      }
    }
    void insert(int r, int l, int time) {
      if(r == -1)
        return;
      mp[r].a = time;
      mp[r].x0 = shop[r].x;
      mp[r].xmax = (shop[r].x + l) / 2;
    }
    void solve(int parametrudetimp = 0) {
      if(slope.size())
        slope.erase(slope.begin(), slope.end());
      vector<tuple<int,int,int,int> >events;
      for(int i = 0; i < n; i++) {
        events.push_back({shop[i].a, shop[i].x, i, shop[i].c});
        events.push_back({shop[i].b + 1, shop[i].x, i, -shop[i].c});
      }
      sort(events.begin(), events.end());
      for(auto [t, x, i, c] : events) {
        if(c > 0) {
          if(1 <= x && x <= 2e8) {
            auto r = line[c].upper_bound({x, i});
            auto l = r;
             --l;
            erase(r -> second, t);
            insert(r -> second, x, t);
            insert(i, l -> first, t);  
          }
          line[c].insert({x, i});      
        }
        else {
          c = -c;
          if(1 <= x && x <= 2e8) {
            auto r = line[c].upper_bound({x ,i});
            auto l = r;
            --l;
            erase(r -> second,  t);
            erase(i, t);
            insert(r -> second, l -> first, t);
          }
          line[c].erase({x, i});
        }
      }
      APPLY::apply(slope);
      if(parametrudetimp == 0) {
        //#error fa revese
        for(int i = 0; i < n; i++)
          shop[i].x = maxx - shop[i].x;
        for(int i = 0; i < q; i++)  
          qs[i].l = maxx - qs[i].l;
        solve(parametrudetimp + 1);
      }
      return;
    }
  }
  namespace PRINT {
    void print() {
      for(int i = 0; i < q; i++)  
        cout << (qs[i].rez == ERROR? -1 : qs[i].rez / 2) << '\n';
      return;
    }
  }
};

int main() {
  ::READ::read();
  ::NORMALIZE::normalize();
  ::INVALIDATE::invalidate();
  ::MAKESEGMENTS::solve();
  ::PRINT::print();
}

Compilation message (stderr)

new_home.cpp: In function 'void {anonymous}::INVALIDATE::invalidate()':
new_home.cpp:51:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   51 |         for(auto [a, b] : smen[i])
      |                  ^
new_home.cpp: In function 'void {anonymous}::AINT::push(int, int, int, int, int, int)':
new_home.cpp:98:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   98 |       int mid = cl + cr >> 1;
      |                 ~~~^~~~
new_home.cpp: In function 'int {anonymous}::AINT::query(int, int, int, int)':
new_home.cpp:105:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  105 |       int mid = cl + cr >> 1;
      |                 ~~~^~~~
new_home.cpp: In function 'void {anonymous}::APPLY::apply(std::vector<{anonymous}::Slope>)':
new_home.cpp:122:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<{anonymous}::Slope>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |       for(int i = 0; i < slope.size(); i++)
      |                      ~~^~~~~~~~~~~~~~
new_home.cpp: In function 'void {anonymous}::MAKESEGMENTS::solve(int)':
new_home.cpp:173:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  173 |       for(auto [t, x, i, c] : events) {
      |                ^

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 20