| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 638912 |
2022-09-07T22:11:57 Z |
beedle |
Plahte (COCI17_plahte) |
C++17 |
|
295 ms |
524288 KB |
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <set>
#include <iterator>
#include <stack>
#include <map>
#include <math.h>
#include <bitset>
#include <deque>
#include <string>
#include <tuple>
#include <queue>
#include <numeric>
#include <unordered_set>
#include <unordered_map>
#define PI 3.141592653589793238
#define ll long long
#define ld long double
#define rep(i, a, b) for (long long i = a; i <= b; i++)
#define mod 998244353ll
#define INF 5e18
#define pb push_back
#define ff first
#define ss second
#define endl '\n'
#define all(x) (x).begin (), (x).end ()
#define sz(x) (ll) (x).size ()
#define reunique(v) v.resize(std::unique(v.begin(), v.end()) - v.begin())
#define rank rnk
#define log lg
#define fast \
ios_base::sync_with_stdio (false); \
cin.tie (NULL); \
cout.tie (NULL)
using namespace std;
struct seg
{
int id, x, lowy, upy;
bool type; // 0 for open, 1 for close
bool operator< (const seg &s) const
{
if(this->x!=s.x)
return this->x<s.x;
else
return this->lowy<s.lowy;
}
};
const int MAXN=4*80000+100;
vector <int> cols[MAXN];
vector <int> adj[MAXN];
int parent[MAXN];
bool marked[MAXN];
int t[10*MAXN+40];
void build(int a[], int v, int tl, int tr) {
if (tl == tr) {
t[v] = a[tl];
} else {
int tm = (tl + tr) / 2;
build(a, v*2, tl, tm);
build(a, v*2+1, tm+1, tr);
t[v] = -1;
}
}
void push(int v) {
if (t[v]!=-1) {
t[v*2] = t[v*2+1] = t[v];
t[v]=-1;
}
}
void update(int v, int tl, int tr, int l, int r, int new_val) {
if (l > r)
return;
if (l == tl && tr == r) {
t[v] = new_val;
} else {
push(v);
int tm = (tl + tr) / 2;
update(v*2, tl, tm, l, min(r, tm), new_val);
update(v*2+1, tm+1, tr, max(l, tm+1), r, new_val);
}
}
int get(int v, int tl, int tr, int pos) {
if (tl == tr) {
return t[v];
}
push(v);
int tm = (tl + tr) / 2;
if (pos <= tm)
return get(v*2, tl, tm, pos);
else
return get(v*2+1, tm+1, tr, pos);
}
set <int> *col_set[MAXN];
int ans[MAXN];
void dfs(int v)
{
marked[v]=true;
col_set[v]=new set <int> ();
for(auto x:cols[v])
col_set[v]->insert(x);
for(auto u:adj[v])
if(!marked[u])
{
dfs(u);
if(sz(*col_set[v])<sz(*col_set[u]))
{
for(auto x:*col_set[v])
col_set[u]->insert(x);
col_set[v]=col_set[u];
}
else
{
for(auto x:*col_set[u])
col_set[v]->insert(x);
}
}
ans[v]=sz(*col_set[v]);
}
signed main()
{
fast;
freopen("hillwalk.in","r",stdin);
freopen("hillwalk.out","w",stdout);
int n,m;
cin>>n>>m;
set <int> n_s;
int x1[n+1],y1[n+1],x2[n+1],y2[n+1];
rep(i,1,n)
{
cin>>x1[i]>>y1[i]>>x2[i]>>y2[i];
n_s.insert(x1[i]);
n_s.insert(x2[i]);
n_s.insert(y1[i]);
n_s.insert(y2[i]);
}
int bx[m+1],by[m+1],bcol[m+1];
rep(i,1,m)
{
cin>>bx[i]>>by[i]>>bcol[i];
n_s.insert(bx[i]);
n_s.insert(by[i]);
}
int cnt=2;
map <int,int> n_m;
for(auto x:n_s)
n_m[x]=cnt, cnt+=2;
int mx=cnt+100;
seg s[2*n+1];
rep(i,1,n)
{
s[i]={int(i),n_m[x1[i]],n_m[y1[i]],n_m[y2[i]],0};
s[i+n]={int(i),n_m[x2[i]],n_m[y1[i]],n_m[y2[i]],1};
}
// rep(i,1,2*n)
// cout<<s[i].id<<" "<<s[i].x<<" "<<s[i].lowy<<" "<<s[i].upy<<" "<<s[i].type<<endl;
sort(s+1,s+2*n+1);
pair <int,int> pts[m+1];
rep(i,1,m)
pts[i]={n_m[bx[i]],n_m[by[i]]};
map <pair<int,int>,int> col_mp;
rep(i,1,m)
col_mp[pts[i]]=bcol[i];
sort(pts+1,pts+m+1);
int thr[mx];
fill(thr,thr+mx,0);
build(thr,1,0,mx-1);
int pidx=1;
rep(i,1,2*n)
{
while(pidx<=m && (s[i].type?(pts[pidx]<=make_pair(s[i].x,s[i].upy)):(pts[pidx]<make_pair(s[i].x,s[i].lowy))))
{
int vertex=get(1,0,mx-1,pts[pidx].ss);
cols[vertex].pb(col_mp[pts[pidx]]);
pidx++;
}
int par=get(1,0,mx-1,s[i].upy+1);
if(!s[i].type)
{
if(par!=0)
{
adj[s[i].id].pb(par);
adj[par].pb(s[i].id);
parent[s[i].id]=par;
}
update(1,0,mx-1,s[i].lowy,s[i].upy,s[i].id);
}
else
{
update(1,0,mx-1,s[i].lowy,s[i].upy,par);
}
}
rep(i,1,n)
if(!marked[i])
{
int curr=i;
while(parent[curr]!=0)
curr=parent[curr];
dfs(curr);
}
rep(i,1,n)
cout<<ans[i]<<endl;
return 0;
}
Compilation message
plahte.cpp: In function 'int main()':
plahte.cpp:141:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
141 | freopen("hillwalk.in","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
plahte.cpp:142:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
142 | freopen("hillwalk.out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
295 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
196 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
203 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
191 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
196 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
