| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 52929 |
2018-06-27T07:55:32 Z |
polyfish |
Plahte (COCI17_plahte) |
C++14 |
|
206 ms |
34568 KB |
//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
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) {
~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
56 ms |
12024 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
60 ms |
14372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
99 ms |
20512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
158 ms |
29768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
206 ms |
34568 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
