Submission #1096729

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096729		Perl32	Plahte (COCI17_plahte)	C++14	160 / 160	233 ms	34752 KiB

plahte

//I wrote this code 4 u <3
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

struct Info {
   int v = -1;
   Info() = default;
   Info(int x) : v(x) {}
};

Info operator+(const Info &a, const Info &b) {
   Info ret;
   ret.v = a.v + b.v;
   return ret;
}

struct Tag {
   int v = -1;
   bool s = 0;

   Tag() = default;
   explicit Tag(int x) {
      v = x;
      s = 1;
   }
};

void apply(Info &a, Tag b) {
   if (b.s) a.v = b.v;
}

void apply(Tag &a, Tag b) {
   if (b.s) a = b;
}

template<class Info, class Tag, class Merge = plus<Info>>
class LazySegTree {
 public:
   int sz;
   const Merge merge;
   vector<Info> t;
   vector<Tag> tag;

   LazySegTree() = default;

   LazySegTree(int n, const Info &v = Info()) : merge(Merge()) {
      sz = 1;
      while (sz < n) sz <<= 1;
      t.assign(sz << 1, Info());
      tag.assign(sz << 1, {});
      for (int i = 0; i < n; ++i) {
         t[i + sz] = v;
      }
      for (int i = sz - 1; i > 0; --i) {
         pull(i);
      }
   }

   LazySegTree(const vector<Info> &a) : merge(Merge()) {
      sz = 1;
      while (sz < (int) a.size()) sz <<= 1;
      t.resize(sz << 1), tag.assign(sz << 1, {});
      for (int i = 0; i < int(a.size()); ++i) {
         t[i + sz] = a[i];
      }
      for (int i = sz - 1; i > 0; --i) {
         pull(i);
      }
   }

   void pull(int x) {
      t[x] = merge(t[x << 1], t[x << 1 | 1]);
   }

   void apply(int p, const Tag &v) {
      ::apply(t[p], v);
      ::apply(tag[p], v);
   }

   void push(int x) {
      apply(x << 1, tag[x]);
      apply(x << 1 | 1, tag[x]);
      tag[x] = Tag();
   }

   Info get(int l, int r, int x, int lx, int rx) {
      if (l >= rx || lx >= r) {
         return Info();
      }
      if (l <= lx && rx <= r) {
         return t[x];
      }
      int m = (lx + rx) >> 1;
      push(x);
      return merge(get(l, r, x << 1, lx, m), get(l, r, x << 1 | 1, m, rx));
   }

   Info get(int l, int r) {
      return get(l, r, 1, 0, sz);
   }

   Info get(int i, int x, int lx, int rx) {
      if (lx + 1 == rx) {
         return t[x];
      }
      int m = (lx + rx) >> 1;
      push(x);
      if (i < m) {
          return get(i, x << 1, lx, m);
      } else {
          return get(i, x << 1 | 1, m, rx);
      }
   }

   Info get(int i) {
      return get(i, 1, 0, sz);
   }

   void upd(int l, int r, const Tag v, int x, int lx, int rx) {
      if (l >= rx || lx >= r) {
         return;
      }
      if (l <= lx && rx <= r) {
         apply(x, v);
         return;
      }
      int m = (lx + rx) >> 1;
      push(x);
      upd(l, r, v, x << 1, lx, m);
      upd(l, r, v, x << 1 | 1, m, rx);
      pull(x);
   }

   void upd(int l, int r, Tag v) {
      upd(l, r, v, 1, 0, sz);
   }

   void upd(int i, Info v, int x, int lx, int rx) {
      if (lx + 1 == rx) {
         t[x] = v;
         return;
      }
      int m = (lx + rx) >> 1;
      push(x);
      if (i < m) {
          upd(i, v, x << 1, lx, m);
      } else {
          upd(i, v, x << 1 | 1, m, rx);
      }
      pull(x);
   }

   void upd(int i, Info v) {
      upd(i, v, 1, 0, sz);
   }
};

signed main(int32_t argc, char *argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<int> srt;
    vector<array<int, 5>> ev(2 * n + m);
    for (int i = 0; i < n; ++i) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        srt.push_back(y1);
        srt.push_back(y2);
        ev[i << 1] = {x1, -1, i, y1, y2};
        ev[i << 1 | 1] = {x2, 1, i, y1, y2};
    }
    for (int i = 0; i < m; ++i) {
        int x, y, c;
        cin >> x >> y >> c;
        srt.push_back(y);
        ev[2 * n + i] = {x, 0, i, y, c};
    }
    sort(srt.begin(), srt.end());
    srt.resize(unique(srt.begin(), srt.end()) - srt.begin());
    vector<set<int>> pizda(n);
    vector<vector<int>> g(n);
    vector<int> par(n, -1);
    LazySegTree<Info, Tag> st(srt.size());
    sort(ev.begin(), ev.end());
    for (auto [x, t, i, y1, y2] : ev) {
        if (t == -1) {
            y1 = lower_bound(srt.begin(), srt.end(), y1) - srt.begin();
            y2 = lower_bound(srt.begin(), srt.end(), y2) - srt.begin();
            par[i] = st.get(y1).v;
            if (par[i] > -1) g[par[i]].push_back(i);
            st.upd(y1, y2 + 1, Tag(i));
        } else if (!t) {
            y1 = lower_bound(srt.begin(), srt.end(), y1) - srt.begin();
            int kek = st.get(y1).v;
            if (kek > -1) pizda[kek].insert(y2);
        } else {
            y1 = lower_bound(srt.begin(), srt.end(), y1) - srt.begin();
            y2 = lower_bound(srt.begin(), srt.end(), y2) - srt.begin();
            st.upd(y1, y2 + 1, Tag(par[i]));
        }
    }
    vector<int> ans(n);
    auto Dfs = [&](auto&& self, int u) -> void {
        for (auto to : g[u]) {
            self(self, to);
            if (pizda[u].size() < pizda[to].size()) swap(pizda[u], pizda[to]);
            while (!pizda[to].empty()) {
                int x = *pizda[to].begin(); pizda[to].erase(pizda[to].begin());
                pizda[u].insert(x);
            }
        }
        ans[u] = pizda[u].size();
    };
    for (int i = 0; i < n; ++i) {
        if (par[i] == -1) Dfs(Dfs, i);
    }
    for (auto x : ans) cout << x << '\n';
}

/*

 */

Compilation message (stderr)

plahte.cpp: In function 'int main(int32_t, char**)':
plahte.cpp:189:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  189 |     for (auto [x, t, i, y1, y2] : ev) {
      |               ^

• Subtask 1: 32 / 32
• Subtask 2: 32 / 32
• Subtask 3: 32 / 32
• Subtask 4: 32 / 32
• Subtask 5: 32 / 32