| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 412505 |
2021-05-27T02:44:00 Z |
pure_mem |
Plahte (COCI17_plahte) |
C++14 |
|
215 ms |
26664 KB |
#include <bits/stdc++.h>
#define ll long long
#define X first
#define Y second
#define MP make_pair
#define double long double
using namespace std;
const int N = 1e5 + 12;
int n, m;
pair< pair<int, int>, pair<int, int> > p[N];
vector< pair< int, pair<pair<int, int>, int> > > g1;
vector< pair< pair<int, int>, int > > g2;
vector< int > graph[N], clr[N];
int answer[N], was[N], last[N], T, res;
void add(int u){
for(int v: clr[u]){
if(last[v] != T) last[v] = T, res++;
}
}
void rest(){
T++, res = 0;
}
void inputs(){
cin >> n >> m;
for(int i = 1;i <= n;i++){
cin >> p[i].X.X >> p[i].X.Y >> p[i].Y.X >> p[i].Y.Y;
g1.push_back(MP(p[i].X.X, MP(MP(p[i].X.Y, p[i].Y.Y), -i)));
g1.push_back(MP(p[i].Y.X, MP(MP(p[i].X.Y, p[i].Y.Y), i)));
}
unordered_map<int, int> mp;
for(int i = 1, x, y, z;i <= m;i++){
cin >> x >> y >> z;
if(!mp[z]) mp[z] = mp.size();
z = mp[z];
g2.push_back(MP(MP(x, y), z));
}
sort(g1.begin(), g1.end()), sort(g2.begin(), g2.end());
set< pair< pair<int, int>, int > > active, active2;
for(int i = 0, j = 0;i < g1.size() || j < g2.size();){
if(i < g1.size() && (j == g2.size() || (g1[i].X < g2[j].X.X || (g1[i].X == g2[j].X.X && g1[i].Y.X.X <= g2[j].X.Y)))){
if(g1[i].Y.Y < 0){
auto it = active.insert(MP(g1[i].Y.X, -g1[i].Y.Y)).X;
active2.insert(MP(MP(g1[i].Y.X.Y, g1[i].Y.X.X), -g1[i].Y.Y));
if(it != active.begin()){
it--;
pair<int, int> lm = it->X;
if(lm.X <= g1[i].Y.X.X && g1[i].Y.X.Y <= lm.Y){
graph[it->Y].push_back(-g1[i].Y.Y);
}
}
}
else{
if(j < g2.size() && g1[i].X == g2[j].X.X && g1[i].Y.X.Y >= g2[j].X.Y) goto mans;
active.erase(MP(g1[i].Y.X, g1[i].Y.Y));
active2.erase(MP(MP(g1[i].Y.X.Y, g1[i].Y.X.X), g1[i].Y.Y));
}
i++;
}
else{
mans:
auto it = active.upper_bound(MP(MP(g2[j].X.Y + 1, -1), -1));
if(it != active.begin()){
it--;
pair<int, int> lm = it->X;
if(lm.X <= g2[j].X.Y && g2[j].X.Y <= lm.Y){
clr[it->Y].push_back(g2[j].Y);
}
else{
it = active2.lower_bound(MP(MP(g2[j].X.Y, -1), -1));
if(it != active2.end()){
pair<int, int> lm = it->X;
if(lm.Y <= g2[j].X.Y && g2[j].X.Y <= lm.X){
clr[it->Y].push_back(g2[j].Y);
}
}
}
}
j++;
}
}
}
int sz[N], tin[N], tout[N], ord[N], timer;
void dfs1(int v){
timer++;
ord[timer] = v, tin[v] = timer;
was[v] = 1, sz[v] = 1;
for(int to: graph[v]){
dfs1(to);
sz[v] += sz[to];
}
tout[v] = timer;
}
void dfs2(int v, bool keep){
int mx = 0;
for(int to: graph[v]){
if(sz[mx] < sz[to]) mx = to;
}
for(int to: graph[v]){
if(to != mx) dfs2(to, 0);
}
if(mx) dfs2(mx, 1);
add(v);
for(int to: graph[v]){
if(to != mx){
for(int i = tin[to];i <= tout[to];i++) add(ord[i]);
}
}
answer[v] = res;
if(!keep) rest();
}
void prep(){
rest();
for(auto tmp: g1){
int i = -tmp.Y.Y;
if(i < 0 || was[i]) continue;
dfs1(i); dfs2(i, 0);
}
for(int i = 1;i <= n;i++) cout << answer[i] << "\n";
}
int main () {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
inputs();
prep();
}
Compilation message
plahte.cpp: In function 'void inputs()':
plahte.cpp:46:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<std::pair<int, int>, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for(int i = 0, j = 0;i < g1.size() || j < g2.size();){
| ~~^~~~~~~~~~~
plahte.cpp:46:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for(int i = 0, j = 0;i < g1.size() || j < g2.size();){
| ~~^~~~~~~~~~~
plahte.cpp:47:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<std::pair<int, int>, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | if(i < g1.size() && (j == g2.size() || (g1[i].X < g2[j].X.X || (g1[i].X == g2[j].X.X && g1[i].Y.X.X <= g2[j].X.Y)))){
| ~~^~~~~~~~~~~
plahte.cpp:47:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | if(i < g1.size() && (j == g2.size() || (g1[i].X < g2[j].X.X || (g1[i].X == g2[j].X.X && g1[i].Y.X.X <= g2[j].X.Y)))){
| ~~^~~~~~~~~~~~
plahte.cpp:60:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | if(j < g2.size() && g1[i].X == g2[j].X.X && g1[i].Y.X.Y >= g2[j].X.Y) goto mans;
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
60 ms |
8916 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
75 ms |
12556 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
124 ms |
18836 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
206 ms |
26664 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
215 ms |
24444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
