| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 95446 |
2019-02-01T08:40:52 Z |
Retro3014 |
None (JOI15_walls) |
C++17 |
|
35 ms |
1780 KB |
#include <iostream>
#include <algorithm>
#include <vector>
#include <stdio.h>
typedef long long ll;
using namespace std;
int N, M;
struct S{
int a, b;
};
vector<S> v;
vector<int> P;
struct STATE{
STATE (int idx, int type, int data) : idx(idx), type(type), data(data) {}
int idx;
int type;
int data;
};
void solve1(){
ll ans = 0;
int x = v[0].a, y = v[0].b;
for(int i=0; i<P.size(); i++){
int now = P[i];
if(y<now){
ans += (ll)now-y;
x += now-y;
y = now;
}else if(x>now){
ans += (ll)x-now;
y -= x-now;
x = now;
}
}
printf("%lld", ans);
}
vector<STATE> st;
vector<int> len;
vector<ll> ans1, ans2, ans;
pair<int, int> calc(int x){
int s = 0, e = st.size()-1, m;
while(s<e){
m = (s+e)/2+1;
if(st[m].idx>=x){
s = m;
}else{
e = m-1;
}
}
pair<int, int> ret;
if(st[s].type==1){
ret.first = st[s].data;
ret.second = st[s].data+len[x]-1;
}else{
ret.first = st[s].data-len[x]+1;
ret.second = st[s].data;
}
return ret;
}
void solve2(){
for(int i=0; i<v.size(); i++){
len.push_back(v[i].b-v[i].a+1);
ans.push_back((ll)0);
ans1.push_back((ll)0);
ans2.push_back((ll)0);
}sort(len.begin(), len.end());
st.push_back({len.size()-1, 1, 0});
for(int i=0; i<P.size(); i++){
int now = P[i];
pair<int, int> tmp = calc(0);
if(tmp.first<=now && now<=tmp.second) continue;
int s = 0, e = len.size()-1, m;
while(s<e){
m = (s+e)/2+1;
pair<int, int> p = calc(m);
//cout<<'*'<<m<<" "<<p.first<<" "<<p.second<<endl;
if(p.first<=now && now<=p.second){
e = m-1;
}else{
s = m;
}
}
pair<int, int> p = calc(s);
if(p.first>now){
STATE add(s, 1, now);
int prv = 0;
while(1){
STATE out(0, 0, 0);
if(!st.empty() && st.back().idx<=add.idx){
out = st.back(); st.pop_back();
}else{
out.idx = add.idx;
out.type = st.back().type;
out.data = st.back().data;
}
if(out.type==1){
ans1[out.idx]+=out.data-add.data;
if(prv!=0) ans1[prv-1]-=(out.data-add.data);
}else{
ans1[out.idx]+=(out.data-add.data+1);
ans2[out.idx]++;
if(prv!=0){
ans1[prv-1]-=(out.data-add.data+1);
ans2[prv-1]--;
}
}
prv = out.idx+1;
if(out.idx==add.idx) break;
}
st.push_back(add);//cout<<add.idx<<" "<<add.data<<" "<<add.type<<endl;
}else{
STATE add(s, 2, now);
int prv = 0;
while(1){
STATE out(0, 0, 0);
if(!st.empty() && st.back().idx<=add.idx){
out = st.back(); st.pop_back();
}else{
out.idx = add.idx;
out.type = st.back().type;
out.data = st.back().data;
}
if(out.type==2){
ans1[out.idx]+=add.data-out.data;
if(prv!=0) ans1[prv-1]-=(add.data-out.data);
}else{
ans1[out.idx]+=(add.data-out.data+1);
ans2[out.idx]++;
if(prv!=0){
ans1[prv-1]-=(add.data-out.data+1);
ans2[prv-1]--;
}
}
prv = out.idx+1;
if(out.idx==add.idx) break;
}
st.push_back(add);//cout<<add.idx<<" "<<add.data<<" "<<add.type<<endl;
}
}
for(int i=ans1.size()-2; i>=0; i--){
ans1[i] += ans1[i+1]; ans2[i] += ans2[i+1];
ans[i] = ans1[i] - (ll)len[i] * ans2[i];
}/*
for(int i=0; i<ans1.size(); i++){
if(i!=0){
ans1[i] += ans1[i-1];
ans2[i] += ans2[i-1];
}
ans[i] = ans1[i] - (ll)len[i] * ans2[i];
}*/
for(int i=0; i<v.size(); i++){
int s = 0, e = len.size()-1, m = 0;
while(s<e){
m = (s+e)/2;
if(len[m] == (v[i].b-v[i].a+1)){
s = e = m;
break;
}
if(len[m]>(v[i].b-v[i].a+1)){
e = m-1;
}else{
s = m+1;
}
}
printf("%lld\n", ans[s]);
}
}
void solve3(){
}
int main(){
scanf("%d%d", &N, &M);
for(int i=0; i<N; i++){
S tmp;
scanf("%d%d", &tmp.a, &tmp.b); v.push_back(tmp);
}
for(int i=0; i<M; i++){
int x;
scanf("%d", &x); P.push_back(x);
}
if(N==1){
solve1();
}else solve2();
return 0;
}
Compilation message
walls.cpp: In function 'void solve1()':
walls.cpp:26:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<P.size(); i++){
~^~~~~~~~~
walls.cpp: In function 'void solve2()':
walls.cpp:67:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<v.size(); i++){
~^~~~~~~~~
walls.cpp:73:26: warning: narrowing conversion of '(len.std::vector<int>::size() - 1)' from 'std::vector<int>::size_type {aka long unsigned int}' to 'int' inside { } [-Wnarrowing]
st.push_back({len.size()-1, 1, 0});
~~~~~~~~~~^~
walls.cpp:74:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<P.size(); i++){
~^~~~~~~~~
walls.cpp:158:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<v.size(); i++){
~^~~~~~~~~
walls.cpp: In function 'int main()':
walls.cpp:181:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &N, &M);
~~~~~^~~~~~~~~~~~~~~~
walls.cpp:184:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &tmp.a, &tmp.b); v.push_back(tmp);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
walls.cpp:188:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &x); P.push_back(x);
~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
376 KB |
Output is correct |
| 2 |
Correct |
34 ms |
1516 KB |
Output is correct |
| 3 |
Correct |
34 ms |
1520 KB |
Output is correct |
| 4 |
Correct |
35 ms |
1520 KB |
Output is correct |
| 5 |
Correct |
33 ms |
1520 KB |
Output is correct |
| 6 |
Correct |
33 ms |
1520 KB |
Output is correct |
| 7 |
Correct |
25 ms |
1520 KB |
Output is correct |
| 8 |
Correct |
33 ms |
1520 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
1780 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
376 KB |
Output is correct |
| 2 |
Correct |
34 ms |
1516 KB |
Output is correct |
| 3 |
Correct |
34 ms |
1520 KB |
Output is correct |
| 4 |
Correct |
35 ms |
1520 KB |
Output is correct |
| 5 |
Correct |
33 ms |
1520 KB |
Output is correct |
| 6 |
Correct |
33 ms |
1520 KB |
Output is correct |
| 7 |
Correct |
25 ms |
1520 KB |
Output is correct |
| 8 |
Correct |
33 ms |
1520 KB |
Output is correct |
| 9 |
Incorrect |
21 ms |
1780 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
