| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 364433 |
2021-02-09T06:59:39 Z |
arnold518 |
None (JOI15_walls) |
C++14 |
|
824 ms |
36704 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 2e5;
struct Data
{
int l, r, p;
};
int N, M;
Data A[MAXN+10];
int B[MAXN+10];
int C[MAXN+10], D[MAXN+10];
ll ans2[MAXN+10];
set<pii> S;
set<int> S2;
int getr(int x)
{
if(x==-1) return -1;
auto it=S2.find(x);
assert(it!=S2.end());
it=next(it);
if(it==S2.end()) return -1;
else return *it;
}
int getl(int x)
{
if(x==-1) return -1;
auto it=S2.find(x);
assert(it!=S2.end());
if(it==S2.begin()) return -1;
it=prev(it);
return *it;
}
struct BIT
{
ll tree[MAXN+10];
void update(int i, ll k)
{
for(i=M-i+1; i<=M; i+=(i&-i)) tree[i]+=k;
}
ll query(int i)
{
ll ret=0;
for(i=M-i+1; i>0; i-=(i&-i)) ret+=tree[i];
return ret;
}
}bit1, bit2;
int main()
{
scanf("%d%d", &N, &M);
for(int i=1; i<=N; i++)
{
scanf("%d%d", &A[i].l, &A[i].r);
A[i].p=i;
}
for(int i=1; i<=M; i++) scanf("%d", &B[i]);
M=unique(B+1, B+M+1)-B-1;
vector<int> V;
V.push_back(B[1]);
for(int i=2; i<M; i++)
{
if(B[i-1]<B[i] && B[i+1]<B[i]) V.push_back(B[i]);
else if(B[i-1]>B[i] && B[i+1]>B[i]) V.push_back(B[i]);
}
V.push_back(B[M]);
for(int i=0; i<V.size(); i++) B[i+1]=V[i];
M=V.size();
sort(A+1, A+N+1, [&](const Data &p, const Data &q)
{
return p.r-p.l<q.r-q.l;
});
for(int i=1; i<M; i++)
{
S.insert({abs(B[i+1]-B[i]), i});
bit1.update(i, abs(B[i+1]-B[i]));
bit2.update(i, 1);
}
for(int i=1; i<=M; i++)
{
S2.insert(i);
C[i]=D[i]=B[i];
}
for(int i=2; i<=M; i++)
{
C[i]=max(C[i], C[i-1]);
D[i]=min(D[i], D[i-1]);
}
//for(int i=1; i<=M; i++) printf("%d ", B[i]); printf("\n");
for(int i=1; i<=N; i++)
{
int len=A[i].r-A[i].l+1;
while(S.size()>1 && S.begin()->first<len)
{
int p=S.begin()->second;
int q=getr(p);
int r=getr(q);
if(getl(p)==-1)
{
bit1.update(p, -abs(B[p]-B[q])); bit2.update(p, -1);
S.erase({abs(B[p]-B[q]), p});
S2.erase(p);
}
else if(r!=-1)
{
if(B[p]>B[q])
{
if(B[r]<=B[p])
{
int t=getr(r);
bit1.update(p, -abs(B[p]-B[q])); bit2.update(p, -1);
S.erase({abs(B[p]-B[q]), p});
bit1.update(q, -abs(B[r]-B[q])); bit2.update(q, -1);
S.erase({abs(B[r]-B[q]), q});
if(t!=-1)
{
bit1.update(r, -abs(B[t]-B[r])); bit2.update(r, -1);
S.erase({abs(B[t]-B[r]), r});
bit1.update(p, abs(B[p]-B[t])); bit2.update(p, 1);
S.insert({abs(B[p]-B[t]), p});
}
S2.erase(q);
S2.erase(r);
}
else
{
int t=getl(p);
if(t!=-1)
{
bit1.update(p, -abs(B[p]-B[q])); bit2.update(p, -1);
S.erase({abs(B[p]-B[q]), p});
bit1.update(q, -abs(B[r]-B[q])); bit2.update(q, -1);
S.erase({abs(B[r]-B[q]), q});
bit1.update(t, -abs(B[t]-B[p])); bit2.update(t, -1);
S.erase({abs(B[t]-B[p]), t});
bit1.update(t, abs(B[r]-B[t])); bit2.update(t, 1);
S.insert({abs(B[r]-B[t]), t});
S2.erase(p);
S2.erase(q);
}
else
{
bit1.update(p, -abs(B[p]-B[q])); bit2.update(p, -1);
S.erase({abs(B[p]-B[q]), p});
bit1.update(q, -abs(B[r]-B[q])); bit2.update(q, -1);
S.erase({abs(B[r]-B[q]), q});
bit1.update(p, abs(B[r]-B[p])); bit2.update(p, 1);
S.insert({abs(B[r]-B[p]), p});
S2.erase(q);
}
}
}
else
{
if(B[r]>=B[p])
{
int t=getr(r);
bit1.update(p, -abs(B[p]-B[q])); bit2.update(p, -1);
S.erase({abs(B[p]-B[q]), p});
bit1.update(q, -abs(B[r]-B[q])); bit2.update(q, -1);
S.erase({abs(B[r]-B[q]), q});
if(t!=-1)
{
bit1.update(r, -abs(B[t]-B[r])); bit2.update(r, -1);
S.erase({abs(B[t]-B[r]), r});
bit1.update(p, abs(B[p]-B[t])); bit2.update(p, 1);
S.insert({abs(B[p]-B[t]), p});
}
S2.erase(q);
S2.erase(r);
}
else
{
int t=getl(p);
if(t!=-1)
{
bit1.update(p, -abs(B[p]-B[q])); bit2.update(p, -1);
S.erase({abs(B[p]-B[q]), p});
bit1.update(q, -abs(B[r]-B[q])); bit2.update(q, -1);
S.erase({abs(B[r]-B[q]), q});
bit1.update(t, -abs(B[t]-B[p])); bit2.update(t, -1);
S.erase({abs(B[t]-B[p]), t});
bit1.update(t, abs(B[r]-B[t])); bit2.update(t, 1);
S.insert({abs(B[r]-B[t]), t});
S2.erase(p);
S2.erase(q);
}
else
{
bit1.update(p, -abs(B[p]-B[q])); bit2.update(p, -1);
S.erase({abs(B[p]-B[q]), p});
bit1.update(q, -abs(B[r]-B[q])); bit2.update(q, -1);
S.erase({abs(B[r]-B[q]), q});
bit1.update(p, abs(B[r]-B[p])); bit2.update(p, 1);
S.insert({abs(B[r]-B[p]), p});
S2.erase(q);
}
}
}
}
else
{
bit1.update(p, -abs(B[p]-B[q])); bit2.update(p, -1);
S.erase({abs(B[p]-B[q]), p});
S2.erase(q);
}
}
int t1=upper_bound(C+1, C+M+1, A[i].r)-C;
int t2=lower_bound(D+1, D+M+1, A[i].l, greater<int>())-D;
auto it=S2.lower_bound(min(t1, t2));
ll ans=0;
//printf("%d\n", len);
//for(auto it : S2) printf("%d ", it); printf("\n");
if(it!=S2.end())
{
if(it!=S2.begin())
{
if(B[*prev(it)]>B[*it])
{
ans=abs(B[*it]-A[i].l);
}
else
{
ans=abs(B[*it]-A[i].r);
}
}
else if(next(it)!=S2.end())
{
if(B[*next(it)]>B[*it])
{
ans=abs(B[*it]-A[i].l);
}
else
{
ans=abs(B[*it]-A[i].r);
}
}
//printf("%d %d / %lld %lld %lld / %d\n", A[i].l, A[i].r, ans, bit1.query(*it), bit2.query(*it), *it);
if(S.size()>1 || S.begin()->first>=len)
{
ans+=bit1.query(*it);
ans-=bit2.query(*it)*(len-1);
}
}
ans2[A[i].p]=ans;
}
for(int i=1; i<=N; i++) printf("%lld\n", ans2[i]);
}
Compilation message
walls.cpp: In function 'int main()':
walls.cpp:78:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | for(int i=0; i<V.size(); i++) B[i+1]=V[i];
| ~^~~~~~~~~
walls.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
61 | scanf("%d%d", &N, &M);
| ~~~~~^~~~~~~~~~~~~~~~
walls.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
64 | scanf("%d%d", &A[i].l, &A[i].r);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
walls.cpp:67:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
67 | for(int i=1; i<=M; i++) scanf("%d", &B[i]);
| ~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
1280 KB |
Output is correct |
| 2 |
Correct |
298 ms |
19296 KB |
Output is correct |
| 3 |
Correct |
502 ms |
27508 KB |
Output is correct |
| 4 |
Correct |
449 ms |
27500 KB |
Output is correct |
| 5 |
Correct |
482 ms |
27508 KB |
Output is correct |
| 6 |
Correct |
285 ms |
27360 KB |
Output is correct |
| 7 |
Incorrect |
28 ms |
2944 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
3308 KB |
Output is correct |
| 2 |
Correct |
444 ms |
20260 KB |
Output is correct |
| 3 |
Correct |
137 ms |
11116 KB |
Output is correct |
| 4 |
Correct |
824 ms |
36576 KB |
Output is correct |
| 5 |
Correct |
557 ms |
28384 KB |
Output is correct |
| 6 |
Correct |
802 ms |
36704 KB |
Output is correct |
| 7 |
Correct |
561 ms |
28384 KB |
Output is correct |
| 8 |
Correct |
799 ms |
36576 KB |
Output is correct |
| 9 |
Correct |
108 ms |
10092 KB |
Output is correct |
| 10 |
Correct |
377 ms |
35700 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
1280 KB |
Output is correct |
| 2 |
Correct |
298 ms |
19296 KB |
Output is correct |
| 3 |
Correct |
502 ms |
27508 KB |
Output is correct |
| 4 |
Correct |
449 ms |
27500 KB |
Output is correct |
| 5 |
Correct |
482 ms |
27508 KB |
Output is correct |
| 6 |
Correct |
285 ms |
27360 KB |
Output is correct |
| 7 |
Incorrect |
28 ms |
2944 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
