Submission #95452

#	Time	Username	Problem	Language	Result	Execution time	Memory
95452		Retro3014	방벽 (JOI15_walls)	C++17	55 / 100	348 ms	19488 KiB

walls

#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]+=(ll)out.data-add.data;
					if(prv!=0)	ans1[prv-1]-=(ll)(out.data-add.data);
				}else{
					ans1[out.idx]+=(ll)(out.data-add.data+1);
					ans2[out.idx]++;
					if(prv!=0){
						ans1[prv-1]-=(ll)(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]+=(ll)add.data-out.data;
					if(prv!=0)	ans1[prv-1]-=(ll)(add.data-out.data);
				}else{
					ans1[out.idx]+= (ll) (add.data-out.data+1);
					ans2[out.idx]++;
					if(prv!=0){
						ans1[prv-1]-= (ll) (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()-1; i>=0; i--){
		if(i!=ans1.size()-1){
			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 (stderr)

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:148:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i!=ans1.size()-1){
      ~^~~~~~~~~~~~~~~
walls.cpp:160: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:183: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:186: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:190: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);
   ~~~~~^~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 45 / 45
• Subtask 3: 0 / 45