#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
pii delta[4] ={{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
vector<pii> find_adj(pii pos){
vector<pii> res;
for(int i = 0; i<4; i++){
res.push_back({pos.first+delta[i].first, pos.second + delta[i].second});
}
return res;
}
map<pii, int> next(map<pii, int> cur){
map<pii, int> res;
for(auto e: cur){
if(e.second >0){
res[e.first] =e.second-1;
}
}
for(auto e: cur){
if(e.second ==2){
for(auto ee: find_adj(e.first)){
if(res.find(ee)==res.end()){
res[ee] = 2;
}
}
}
}
return res;
}
const int sz= 10;
void display(map<pii, int>&m){
for(int i = -sz; i<=sz; i++){
for(int j = -sz; j<=sz; j++){
if(m.find({i, j})!=m.end()){
//cout<<m[{i, j}];
}
else{
//cout<<"0";
}
}
//cout<<endl;
}
//cout<<endl;
}
struct DSU{
vector<int> dsu;
vector<int> sz;
vector<pii> interval;
vector<int> pos;
int ca =0;
int cb= 0;
void init(int len, vector<int>&p){
dsu.resize(len);
sz.resize(len);
for(int i = 0; i<len; i++){
dsu[i] = i;
sz[i] =1;
}
interval.resize(len);
pos = p;
for(int i = 0; i<len; i++){
interval[i] = {pos[i], pos[i]};
}
ca= len*4;
}
int c(int u){
if(dsu[u] == u){
return u;
}
int r= c(dsu[u]);
dsu[u]= r;
return r;
}
int merge(int a, int b, int t){
//cout<<a<<" "<<b<<" "<<endl;
a= c(a);
b= c(b);
//cout<<"before "<<ca<<"x + "<<cb<<endl;
ca-= 2;
cb-=-2;
ca -= 4;
cb -= 2*(interval[a].second-interval[a].first+1) + 2*(interval[b].second-interval[b].first+1);
if(sz[a]<sz[b]){
swap(a, b);
}
dsu[b] = a;
sz[a]+=b;
interval[a] = {min(interval[a].first, interval[b].first), max(interval[a].second, interval[b].second)};
ca +=2;
cb += 2*(interval[a].second-interval[a].first+1);
//cout<<"after "<<ca<<"x + "<<cb<<endl;
return t-1;
}
};
signed main(){
int n, q;
cin>>n>>q;
vector<int> pos;
map<pii, int> cur;
bool diag= true;
for(int i = 0; i<n; i++){
int x, y;
cin>>x>>y;
pos.push_back(x);
cur[{x, y}] = 2;
if(x!=y){
diag= false;
}
}
if(diag){
sort(pos.begin(), pos.end());
vector<pii> distances;
map<int, pair<int, pii>> formulas;
DSU ds;
ds.init(n, pos);
int kept= 0;
for(int i = 0; i<n-1; i++){
distances.push_back({pos[i+1]-pos[i], i});
}
int cur_t= -1;
for(int i = 0;i<n-1; i++){
if(distances[i].first != cur_t){
formulas[cur_t] = {kept, {ds.ca, ds.cb}};
kept= 0;
cur_t =distances[i].first;
}
kept += ds.merge(distances[i].second, distances[i].second+1, distances[i].first);
}
formulas[cur_t] = {kept, {ds.ca, ds.cb}};
for(auto e: formulas){
//cout<<"at time "<<e.first<<" formula "<<e.second.second.first<<" "<<e.second.second.second<<" +("<<e.second.first<<endl;
}
for(int i = 0; i<q; i++){
int t;
cin>>t;
if(t==0){
cout<<n<<endl;
continue;
}
auto it = --formulas.upper_bound(t);
auto e= *(it);
//cout<<"at time "<<t<<" formula "<<e.second.second.first<<" "<<e.second.second.second<<" +("<<e.second.first<<endl;
int res= 0;
if(it->first == t){
res += it->second.first;
}
res += it->second.second.first*t + it->second.second.second;
cout<<res<<endl;
}
}
else{
vector<int> ans(1000+1, -1);
int r;
for(int steps= 0; steps<1000+1; steps++){
r=0;
for(auto e: cur){
if(e.second ==2){
r++;
}
}
ans[steps] = r;
cur = next(cur);
}
int max_s= 0;
for(int i = 0; i<q; i++){
int steps= 0;
cin>>steps;
cout<<ans[steps]<<endl;
}
}
}
Compilation message
cell.cpp: In function 'int main()':
cell.cpp:154:18: warning: variable 'e' set but not used [-Wunused-but-set-variable]
154 | for(auto e: formulas){
| ^
cell.cpp:166:18: warning: variable 'e' set but not used [-Wunused-but-set-variable]
166 | auto e= *(it);
| ^
cell.cpp:193:13: warning: unused variable 'max_s' [-Wunused-variable]
193 | int max_s= 0;
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1518 ms |
2676 KB |
Output is correct |
| 2 |
Correct |
1610 ms |
2784 KB |
Output is correct |
| 3 |
Correct |
1755 ms |
3048 KB |
Output is correct |
| 4 |
Correct |
1784 ms |
2816 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1518 ms |
2676 KB |
Output is correct |
| 2 |
Correct |
1610 ms |
2784 KB |
Output is correct |
| 3 |
Correct |
1755 ms |
3048 KB |
Output is correct |
| 4 |
Correct |
1784 ms |
2816 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
127 ms |
18284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
127 ms |
18284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8055 ms |
9268 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
8055 ms |
9268 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1518 ms |
2676 KB |
Output is correct |
| 2 |
Correct |
1610 ms |
2784 KB |
Output is correct |
| 3 |
Correct |
1755 ms |
3048 KB |
Output is correct |
| 4 |
Correct |
1784 ms |
2816 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
