제출 #1110000

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1110000		PVSekhar	Plahte (COCI17_plahte)	C++14	0 / 160	474 ms	62012 KiB

plahte

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 80000 + 2;

template<class T>
struct Point{
	T x, y;
	Point (const ll &x_ = 0, const ll &y_ = 0) : x(x_), y(y_) {};
    
	bool operator<(const Point &p) const{
    	return x < p.x || (x == p.x && y < p.y);
	}
	bool operator==(const Point &p) const{
    	return x == p.x && y == p.y;
	}
};

using Pt = Point<ll>;

struct Line {
	ll x1, y1, x2, y2, ind;
	Line (const ll &x1_ = 0, const ll &y1_ = 0, const ll &x2_ = 0, const ll &y2_ = 0, const ll &ind_ = 0) : x1(x1_), y1(y1_), x2(x2_), y2(y2_), ind(ind_) {};
    
	bool operator==(const Line &l) const {
    	return ind == l.ind;
	}
	bool operator<(const Line &l) const {
    	return ind != l.ind && (x1 < l.x1 || (x1 == l.x1 && y1 < l.y1));
	}
};

struct SEGTREE {
    ll def = N - 1;
    vector<ll> tree, lazy;
    SEGTREE(int n_) {
        for (int i = 0; i < 4 * n_; i++) tree.push_back(0);
        for (int i = 0; i < 4 * n_; i++) lazy.push_back(def);
    }
    void prop(int node, int i, int j) {
        if (lazy[node] == -1) return;
        tree[node] = (j - i + 1) * lazy[node];
        if (i != j) {
            lazy[node << 1] = lazy[node];
            lazy[node << 1 | 1] = lazy[node];
        }
        lazy[node] = -1;
    }
    void update(int node, int i, int j, int l, int r, int val) {
        if (i > j || i > r || l > r || l > j) return;
        if (l <= i && j <= r) {
            lazy[node] = val;
            prop(node, i, j);
            return;
        }
        int mid = (i + j) / 2;
        prop(node << 1, i, mid);
        prop(node << 1 | 1, mid + 1, j);
        update(node << 1, i, mid, l, r, val);
        update(node << 1 | 1, mid + 1, j, l, r, val);
        tree[node] = tree[node << 1] + tree[node << 1 | 1];
    }
    int query(int node, int i, int j, int ind) {
        prop(node, i, j);
        if (i == j) {
            return tree[node];
        }
        int mid = (i + j) / 2;
        prop(node << 1, i, mid);
        prop(node << 1 | 1, mid + 1, j);
        tree[node] = tree[node << 1] + tree[node << 1 | 1];
        if (ind <= mid) return query(node << 1, i, mid, ind);
        else return query(node << 1 | 1, mid + 1, j, ind);
    }
} segtree(3 * N);

ll n, m;
vector<Line> recs;
vector<set<ll>> c_set(N);
vector<ll> c_ind(N), p(N, N - 1), ans(N, -1);
vector<pair<Pt, ll>> pts;
vector<vector<ll>> edges(N);
map<ll, ll> y_ind;

void merge(ll node, ll parent) {
    if (c_set[c_ind[node]].size() > c_set[c_ind[parent]].size()) {
        for (ll x : c_set[c_ind[parent]]) c_set[c_ind[node]].insert(x);
        c_ind[parent] = c_ind[node];
    } else {
        for (ll x : c_set[c_ind[node]]) c_set[c_ind[parent]].insert(x);
    }
}

ll find_p(ll y) {
    return segtree.query(1, 1, 3 * N, y);
}

void sweep() {
    set<Pt> s;
    Pt pt;
    ll ind;
    for (auto x : pts) {
        pt = x.first, ind = x.second;
        ll par = find_p(y_ind[pt.y]);
        if (ind < 0) {
            if (par != N - 1) c_set[c_ind[par]].insert(ind);
        } else if (s.find(Pt(recs[ind].x1, recs[ind].y1)) == s.end()) {
            s.insert(pt);
            edges[ind].push_back(par);
            edges[par].push_back(ind);
            segtree.update(1, 1, 3 * N, y_ind[recs[ind].y1], y_ind[recs[ind].y2], ind);
        } else {
            s.erase(Pt(recs[ind].x1, recs[ind].y1));
            segtree.update(1, 1, 3 * N, y_ind[recs[ind].y1], y_ind[recs[ind].y2], p[ind]);
        }
    }
}

void dfs(ll node, ll parent) {
    for (ll child : edges[node]) {
        if (child == parent) continue;
        dfs(child, node);
    }
    if (node != N - 1) ans[node] = c_set[c_ind[node]].size();
    if (node != N - 1 && parent != N - 1) merge(node, parent);
}

void solve() {
	ll a, b, c, d;
	cin >> n >> m;
    vector<ll> ys;
	for (ll i = 0; i < n; i++) {
    	cin >> a >> b >> c >> d;
    	recs.push_back(Line(a, b, c, d, i));
    	pts.push_back(make_pair(Pt(a, b), i));
    	pts.push_back(make_pair(Pt(c, d), i));
        ys.push_back(b);
        ys.push_back(d);
        c_ind[i] = i;
	}
	for (ll i = 0; i < m; i++) {
    	cin >> a >> b >> c;
        ys.push_back(b);
    	pts.push_back(make_pair(Pt(a, b), -c));
	}
	sort(pts.begin(), pts.end());
	sort(ys.begin(), ys.end());
    for (ll i = 0; i < ys.size(); i++) {
        y_ind[ys[i]] = i + 1;
    }
    sweep();
    dfs(N - 1, -1);
    for (ll i = 0; i < n; i++) cout << ans[i] << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
	ll t = 1;
	// cin >> t;
	while(t--) {
    	solve();
	}
	return 0;
}

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

plahte.cpp: In function 'void solve()':
plahte.cpp:148:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |     for (ll i = 0; i < ys.size(); i++) {
      |                    ~~^~~~~~~~~~~

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