Submission #1271362

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271362		dfhdfhdsf	Plahte (COCI17_plahte)	C++20	160 / 160	289 ms	101976 KiB

plahte

#include <cstdio>
#include <string>
#include <array>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <bitset>
#include <cctype>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;
#define TASK "tet"
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define FORD(i,a,b) for(int i=a;i>=b;--i)
#define endl "\n"
#define spa " "
#define isz(s) (int) (s).size()
#define ALL(x) x.begin(),x.end()
const int N = 6e5 + 7;
const ll mod = 1e9 + 7;
const ll inf = 4e18;

int n, m;

struct SegTree {
    int n;
    vector< vector<int> > trace;
    SegTree() { n = 0; }
    SegTree(int _n) { init(_n); }
    void init(int _n) {
        n = _n;
        trace.clear();
        trace.resize(4 * n + 5);
    }
    void update(int id, int l, int r, int u, int v, int w) {
        if (l > v || r < u) return;
        if (l >= u && r <= v) {
            if (w < 0) {
                if (!trace[id].empty()) trace[id].pop_back();
            } else {
                trace[id].push_back(w);
            }
            return;
        }
        int mid = (l + r) >> 1;
        update(id << 1, l, mid, u, v, w);
        update(id << 1 | 1, mid + 1, r, u, v, w);
    }
    int get(int id, int l, int r, int pos) {
        int res = 0;
        while (true) {
            if (!trace[id].empty()) res = trace[id].back();
            if (l == r) break;
            int mid = (l + r) >> 1;
            if (pos <= mid) {
                id = id << 1;
                r = mid;
            } else {
                id = id << 1 | 1;
                l = mid + 1;
            }
        }
        return res;
    }
};

struct Event {
    int x, y1, y2, type;
    bool operator < (const Event &o) const {
        if (x != o.x) return x < o.x;
        return type > o.type;
    }
};

vector<int> g[N];
set<int> sset[N];
int ans_arr[N];

void dfs_collect(int u) {
    for (int v : g[u]) {
        dfs_collect(v);
        if (sset[u].size() < sset[v].size()) swap(sset[u], sset[v]);
        for (int val : sset[v]) sset[u].insert(val);
        sset[v].clear();
    }
    ans_arr[u] = (int)sset[u].size();
}

void input() {
    cin >> n >> m;
}

namespace subf {
    void solve() {
        vector<int> rv;
        vector<Event> raw; raw.reserve(n + m);

        FOR(i,1,n) {
            int x1,y1,x2,y2;
            cin >> x1 >> y1 >> x2 >> y2;
            raw.push_back({x1,y1,x2,y2});
            rv.push_back(x1); rv.push_back(x2);
            rv.push_back(y1); rv.push_back(y2);
        }

        FOR(i,1,m) {
            int a,b,k;
            cin >> a >> b >> k;
            raw.push_back({a,b,k,0});
            rv.push_back(a); rv.push_back(b);
        }

        sort(ALL(rv));
        rv.erase(unique(ALL(rv)),rv.end());
        int sz = isz(rv);

        vector<Event> vt;
        FOR(i,1,n) {
            Event e = raw[i-1];
            int x1c = (int)(lower_bound(ALL(rv), e.x) - rv.begin()) + 1;
            int y1c = (int)(lower_bound(ALL(rv), e.y1) - rv.begin()) + 1;
            int x2c = (int)(lower_bound(ALL(rv), e.y2) - rv.begin()) + 1;
            int y2c = (int)(lower_bound(ALL(rv), e.type) - rv.begin()) + 1;
            vt.push_back({x1c,y1c,y2c,i});
            vt.push_back({x2c,y1c,y2c,-i});
        }
        FOR(i,n+1,n+m) {
            Event e = raw[i-1];
            int xc = (int)(lower_bound(ALL(rv), e.x) - rv.begin()) + 1;
            int yc = (int)(lower_bound(ALL(rv), e.y1) - rv.begin()) + 1;
            vt.push_back({xc,yc,e.y2,0});
        }

        sort(ALL(vt));
        SegTree st(sz);

        FOR(i,0,n) {
            g[i].clear();
            sset[i].clear();
            ans_arr[i] = 0;
        }

        stack<int> roots;
        for (Event e : vt) {
            if (e.type < 0) {
                st.update(1,1,sz,e.y1,e.y2,-1);
            } else if (e.type == 0) {
                int pos = st.get(1,1,sz,e.y1);
                if (pos != 0) sset[pos].insert(e.y2);
            } else {
                int idx = e.type;
                int pos = st.get(1,1,sz,e.y1);
                if (pos != 0) g[pos].push_back(idx);
                else roots.push(idx);
                st.update(1,1,sz,e.y1,e.y2,idx);
            }
        }

        while(!roots.empty()) {
            dfs_collect(roots.top());
            roots.pop();
        }

        FOR(i,1,n) cout << ans_arr[i] << endl;
    }
}

void run() {
    input();
    subf::solve();
}

signed main() {
    cin.tie(NULL)->sync_with_stdio(false);
    if(fopen(TASK".INP","r")) {
        freopen(TASK".INP","r",stdin);
        freopen(TASK".OUT","w",stdout);
    }
    run();
    return 0;
}

Compilation message (stderr)

plahte.cpp: In function 'int main()':
plahte.cpp:189:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  189 |         freopen(TASK".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
plahte.cpp:190:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  190 |         freopen(TASK".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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