| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 224374 |
2020-04-17T18:07:26 Z |
dfistric |
Plahte (COCI17_plahte) |
C++14 |
|
2000 ms |
62800 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;
vector <int> v2,t[525005],p[525005],v3[525005];
//vector <pair<int,int> > v1[160005];
vector <int> v5;
int off=1,parent[525005],cnt1[525005];
map <pair<int,int>,int> m1;
map <int,vector<pair<int,int> > > v1;
set <int> dfs(int x) {
//cout << x << "\n";
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 {
// if(t[x].size() == 0) while(true) {}
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 (x >= 525005) while (true) {}
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) {
// if (x >= 525005) while (true) {}
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));
}
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;
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());
/*cout << "\n";
for(int i=0;i<v.size();i++) {
cout << v[i].first.first << " " << v[i].first.second << " " << v[i].second.first << " " << v[i].second.second << "\n";
}
cout << "abc\n";*/
for(int i=1;i<=v2.size();i++) {
//cout << int(t[10].size()) << "\n";
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();
//cout << "def\n";
while(ind<v.size() && v[ind].first.first==i) {
//cout << int(t[10].size()) << "\n";
if(v[ind].second.first==-1) {
v5.push_back(ind);
/*parent[ind]=query(1,0,off-1,v[ind].first.second,v[ind].first.second);
v3[query(1,0,off-1,v[ind].first.second,v[ind].first.second)-1].push_back(ind);*/
}
else {
//if(ind==5) cout << v[ind].first.second << " " << v[ind].second.second << "\n";
if (ind >= v.size()) while (true) {}
if (parent[ind]-1 >= 525005 || parent[ind]-1 < 0) {ind++; continue;}
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);
//cout << int(t[10].size()) << "\n";
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];
if (ind1 >= v.size()) while (true) {}
if (parent[ind1]-1 >= 525005 || parent[ind1]-1 < 0) while (true) {}
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);
}
}
// while (true) {}
/*for(int i=0;i<v.size();i++) {
cout << parent[i] << "\n";
}
cout << "\n";*/
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";
//cout << "abc\n";
}
//assert(0);
//cout << "123\n";
/*for(int i=0;i<v.size();i++) {
cout << parent[i] << " ";
}*/
return 0;
}
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:34:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<p[x].size();i++) {
~^~~~~~~~~~~~
plahte.cpp:42: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:121:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1;i<=v2.size();i++) {
~^~~~~~~~~~~
plahte.cpp:123:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<v1[i].size();j++) {
~^~~~~~~~~~~~~
plahte.cpp:128:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(ind<v.size() && v[ind].first.first==i) {
~~~^~~~~~~~~
plahte.cpp:137:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (ind >= v.size()) while (true) {}
~~~~^~~~~~~~~~~
plahte.cpp:147:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<v5.size();j++) {
~^~~~~~~~~~
plahte.cpp:149:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (ind1 >= v.size()) while (true) {}
~~~~~^~~~~~~~~~~
plahte.cpp:163:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v.size();i++) {
~^~~~~~~~~
plahte.cpp:77:16: warning: unused variable 'cnt' [-Wunused-variable]
int n,m,ind=0,cnt=0;
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2093 ms |
46048 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2089 ms |
46816 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2093 ms |
53208 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2097 ms |
62644 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2091 ms |
62800 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
