| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 221000 |
2020-04-09T11:49:44 Z |
dfistric |
Plahte (COCI17_plahte) |
C++14 |
|
933 ms |
524292 KB |
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<cassert>
#include<algorithm>
using namespace std;
vector <pair<pair<int,int>,pair<int,int> > > v,v4;
const int MAXN = (1 << 19);
vector <int> v2,t[MAXN],p[MAXN],v3[MAXN];
vector <pair<int,int> > v1[MAXN];
vector <int> v5;
int off=1,parent[MAXN],cnt1[MAXN];
map <pair<int,int>,int> m1;
set <int> dfs(int x) {
set <int> ret,s;
if(v[x].second.first==-1) {
ret.insert(m1[v[x].first]);
return ret;
}
for(int i=0;i<v3[x].size();i++) {
s=dfs(v3[x][i]);
if(ret.size()<s.size()) swap(ret,s);
for(set <int>::iterator it=s.begin();it!=s.end();it++) {
ret.insert(*it);
}
}
cnt1[x]=ret.size();
return ret;
}
void send(int x) {
if(p[x].size()==0) return;
for(int i=0;i<p[x].size();i++) {
if(p[x][i]>0) t[x].push_back(p[x][i]);
else t[x].pop_back();
}
if(x<off) {
for(int i=0;i<p[x].size();i++) {
p[x*2].push_back(p[x][i]);
p[x*2+1].push_back(p[x][i]);
}
}
p[x].clear();
}
void update(int x,int lo,int hi,int l,int r,int v) {
if(lo>r or hi<l) return;
if(lo>=l && hi<=r) {
p[x].push_back(v);
send(x);
return;
}
update(x*2,lo,(lo+hi)/2,l,r,v);
update(x*2+1,(lo+hi)/2+1,hi,l,r,v);
}
int query(int x,int lo,int hi,int l,int r) {
send(x);
if(lo>r or hi<l) return -1;
if(lo>=l && hi<=r) {
if(!t[x].empty()) return t[x].back();
return -1;
}
return max(query(x*2,lo,(lo+hi)/2,l,r),query(x*2+1,(lo+hi)/2+1,hi,l,r));
}
void tle() {
while(true){}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n,m,ind=0,cnt=0;
cin >> n >> m;
for(int i=0;i<n;i++) {
int x1,y1,x2,y2;
cin >> x1 >> y1 >> x2 >> y2;
v2.push_back(x1);
v2.push_back(x2);
v2.push_back(y1);
v2.push_back(y2);
v.push_back(make_pair(make_pair(x1,y1),make_pair(x2,y2)));
}
for(int i=0;i<m;i++) {
int x,y,c;
cin >> x >> y >> c;
m1[make_pair(x,y)]=c;
v2.push_back(x);
v2.push_back(y);
v.push_back(make_pair(make_pair(x,y),make_pair(-1,-1)));
}
// while(off<2*n+m) off*=2;
off = (1 << 18);
sort(v2.begin(),v2.end());
v2.erase(unique(v2.begin(),v2.end()),v2.end());
for(int i=0;i<n+m;i++) {
int a=0;
if(v[i].second.first==-1) a=m1[v[i].first];
v[i].first.first=lower_bound(v2.begin(),v2.end(),v[i].first.first)-v2.begin()+1;
v[i].first.second=lower_bound(v2.begin(),v2.end(),v[i].first.second)-v2.begin()+1;
if(a) m1[v[i].first]=a;
if(v[i].second.first!=-1) {
v[i].second.first=lower_bound(v2.begin(),v2.end(),v[i].second.first)-v2.begin()+1;
v1[v[i].second.first+1].push_back(make_pair(v[i].first.second,v[i].second.second));
}
if(v[i].second.second!=-1) v[i].second.second=lower_bound(v2.begin(),v2.end(),v[i].second.second)-v2.begin()+1;
}
v4=v;
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
for(int i=1;i<=v2.size();i++) {
for(int j=0;j<v1[i].size();j++) {
update(1,0,off-1,v1[i][j].first,v1[i][j].second,-1);
}
v5.clear();
while(ind<v.size() && v[ind].first.first==i) {
if(v[ind].second.first==-1) {
v5.push_back(ind);
}
else {
parent[ind]=query(1,0,off-1,v[ind].first.second,v[ind].second.second);
if(parent[ind]) v3[parent[ind]-1].push_back(ind);
update(1,0,off-1,v[ind].first.second,v[ind].second.second,ind+1);
}
ind+=1;
}
for(int j=0;j<v5.size();j++) {
int ind1=v5[j];
parent[ind1]=query(1,0,off-1,v[ind1].first.second,v[ind1].first.second);
if(parent[ind1]) v3[parent[ind1]-1].push_back(ind1);
}
}
for(int i=0;i<v.size();i++) {
if(parent[i]==-1) dfs(i);
}
for(int i=0;i<n;i++) {
cout << cnt1[int(lower_bound(v.begin(),v.end(),v4[i])-v.begin())] << "\n";
} return 0;
}
/*
4 6
1 2 4 6
5 1 8 5
6 3 7 4
5 7 8 9
3 5 1
3 8 2
6 2 3
7 4 4
5 7 5
7 9 6
*/
Compilation message
plahte.cpp: In function 'std::set<int> dfs(int)':
plahte.cpp:22:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v3[x].size();i++) {
~^~~~~~~~~~~~~
plahte.cpp: In function 'void send(int)':
plahte.cpp:35:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<p[x].size();i++) {
~^~~~~~~~~~~~
plahte.cpp:40:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<p[x].size();i++) {
~^~~~~~~~~~~~
plahte.cpp: In function 'int main()':
plahte.cpp:119:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1;i<=v2.size();i++) {
~^~~~~~~~~~~
plahte.cpp:120:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<v1[i].size();j++) {
~^~~~~~~~~~~~~
plahte.cpp:124:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(ind<v.size() && v[ind].first.first==i) {
~~~^~~~~~~~~
plahte.cpp:135:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<v5.size();j++) {
~^~~~~~~~~~
plahte.cpp:143:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v.size();i++) {
~^~~~~~~~~
plahte.cpp:79:16: warning: unused variable 'cnt' [-Wunused-variable]
int n,m,ind=0,cnt=0;
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
697 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
693 ms |
524288 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
790 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
927 ms |
524288 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
933 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
