Submission #52929

#	Time	Username	Problem	Language	Result	Execution time	Memory
52929		polyfish	Plahte (COCI17_plahte)	C++14	0 / 160	206 ms	34568 KiB

plahte

//I love armpit fetish

#include <bits/stdc++.h>
using namespace std;

#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';
#define PR0(A, n) cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';
#define FILE_NAME "data"
#define y1 _y1_
#define y2 _y2_

const int INF = 7;         ///Notice
const int MAX_N = 80002;

class IT_1D {
public:
	struct node {
		int val;
		node *leftChild, *rightChild;

		node() {
			val = 0;
			leftChild = NULL;
			rightChild = NULL;
		}

		void createChild() {
			if (leftChild==NULL) {
				leftChild = new node();
				rightChild = new node();
			}
		}
	} *root;

	IT_1D() {
		root = new node();
	}

	void upd(int pos, int val, int l, int r, node *cur) {
		if (pos<l || pos>r)
			return;
		if (pos==l && r==pos) {
			cur->val += val;
			return;
		}
        cur->createChild();
		int mid = (l + r) / 2;
		upd(pos, val, l, mid, cur->leftChild);
		upd(pos, val, mid+1, r, cur->rightChild);
		cur->val = cur->leftChild->val + cur->rightChild->val;
	}

	int get(int u, int v, int l, int r, node *cur) {
		if (v<l || u>r || cur->val==0)
			return -1;
		if (l==r)
			return l;
		int mid = (l + r) / 2;
		cur->createChild();
		int tmp = get(u, v, l, mid, cur->leftChild);
		if (tmp>-1)
			return tmp;
		return get(u, v, mid+1, r, cur->rightChild);
	}

	int calc(int u, int v, int l, int r, node *cur) {
        if (v<l || u>r)
            return 0;
        if (u<=l && r<=v)
            return cur->val;
        cur->createChild();
        int mid = (l + r) / 2;
        return calc(u, v, l, mid, cur->leftChild)
                + calc(u, v, mid+1, r, cur->rightChild);
	}

	void upd(int pos, int val) {
		upd(pos, val, 1, INF, root);
	}

	int get(int u, int v) {
		return get(u, v, 1, INF, root);
	}

	int calc(int u, int v) {
        return calc(u, v, 1, INF, root);
	}
};

class IT_2D {
public:
	struct node {
		IT_1D val;
		node *leftChild, *rightChild;

		node() {
			leftChild = NULL;
			rightChild = NULL;
		}

		void createChild() {
			if (leftChild==NULL) {
				leftChild = new node();
				rightChild = new node();
			}
		}
	} *root;

	IT_2D() {
		root = new node();
	}

	void upd(int x, int y, int val, int l, int r, node *cur) {
        if (x<l || x>r)
            return;
        if (x==l && r==x) {
            cur->val.upd(y, val);
            return;
        }
        cur->createChild();
        int mid = (l + r) / 2;
        upd(x, y, val, l, mid, cur->leftChild);
        upd(x, y, val, mid+1, r, cur->rightChild);
        cur->val.upd(y, val);
	}

	pair<int, int> get(int u1, int v1, int u2, int v2, int l, int r, node *cur) {
        if (v1<l || u1>r || cur->val.calc(u2, v2)==0)
            return make_pair(-1, -1);
        if (l==r)
            return make_pair(l, cur->val.get(u2, v2));
        cur->createChild();
        int mid = (l + r) / 2;
        pair<int, int> tmp = get(u1, v1, u2, v2, l, mid, cur->leftChild);
        if (tmp!=make_pair(-1, -1))
            return tmp;
        return get(u1, v1, u2, v2, mid+1, r, cur->rightChild);
	}

	void upd(int x, int y, int val) {
        upd(x, y, val, 1, INF, root);
    }

    pair<int, int> get(int u1, int v1, int u2, int v2) {
        return get(u1, v1, u2, v2, 1, INF, root);
    }
} T1, T2;

struct rect {
    int x1, y1, x2, y2, id;

    bool operator<(const rect &p) {
        return 1LL*(x2-x1)*(y2-y1)<1LL*(p.x2-p.x1)*(p.y2-p.y1);
    }
} r[MAX_N];

int n, m, res[MAX_N];
pair<int, int> paintball[MAX_N];
vector<int> g[MAX_N];
map<pair<int, int>, int> ID, color;
set<int> s[MAX_N];

void enter() {
    cin >> n >> m;
    for (int i=1; i<=n; ++i) {
        cin >> r[i].x1 >> r[i].y1 >> r[i].x2 >> r[i].y2;
        r[i].id = i;
    }
    for (int i=1; i<=m; ++i) {
        cin >> paintball[i].first >> paintball[i].second;
        int c; cin >> c;
        color[paintball[i]] = c;
    }
}

void buildTree() {
    sort(r+1, r+n+1);
    for (int i=1; i<=n; ++i) {
        while (true) {
            pair<int, int> tmp = T1.get(r[i].x1, r[i].x2, r[i].y1, r[i].y2);
            if (tmp==make_pair(-1, -1))
                break;
            g[i].push_back(ID[tmp]);
            T1.upd(tmp.first, tmp.second, -1);
        }
        T1.upd(r[i].x1, r[i].y1, 1);
        ID[make_pair(r[i].x1, r[i].y1)] = i;
    }
}

void addPaintball() {
    for (int i=1; i<=m; ++i) {
        T2.upd(paintball[i].first, paintball[i].second, 1);
    }
    for (int i=1; i<=n; ++i) {
        while (true) {
            pair<int, int> tmp = T2.get(r[i].x1, r[i].x2, r[i].y1, r[i].y2);
            if (tmp==make_pair(-1, -1))
                break;
            s[i].insert(color[tmp]);
            T2.upd(tmp.first, tmp.second, -1);
            //debug(T2.get(1, 7, 1, 7).second);
            //BP();
        }
    }
}

void Merge(int u, int v) {
    if (s[u].size()<s[v].size())
        swap(s[u], s[v]);
    for (set<int>::iterator it=s[v].begin(); it!=s[v].end(); ++it)
        s[u].insert(*it);
}

void solve(int u) {
    //debug(s[u].size());
    for (int i=0; i<g[u].size(); ++i) {
        int v = g[u][i];
        solve(v);
        Merge(u, v);
    }
    res[r[u].id] = s[u].size();
}

int main() {
	//freopen(FILE_NAME".inp", "r", stdin);
	//freopen(FILE_NAME".out", "w", stdout);
	ios::sync_with_stdio(0); cin.tie(0);
    enter();
    buildTree();
    addPaintball();
    memset(res, -1, sizeof(res));
    for (int i=n; i>=1; --i)
        if (res[r[i].id]==-1)
            solve(i);
    for (int i=1; i<=n; ++i)
        cout << res[i] << '\n';
}

Compilation message (stderr)

plahte.cpp: In function 'void solve(int)':
plahte.cpp:219:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<g[u].size(); ++i) {
                   ~^~~~~~~~~~~~

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