답안 #95452 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
95452	2019-02-01T08:47:32 Z	Retro3014	방벽 (JOI15_walls)	C++17	55 / 100	348 ms	19488 KB

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

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.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	35 ms	1520 KB	Output is correct
3	Correct	35 ms	1548 KB	Output is correct
4	Correct	36 ms	1520 KB	Output is correct
5	Correct	36 ms	1520 KB	Output is correct
6	Correct	36 ms	1516 KB	Output is correct
7	Correct	27 ms	1644 KB	Output is correct
8	Correct	31 ms	1520 KB	Output is correct

Subtask #2
45.0 / 45.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	1780 KB	Output is correct
2	Correct	100 ms	4836 KB	Output is correct
3	Correct	155 ms	15724 KB	Output is correct
4	Correct	255 ms	17736 KB	Output is correct
5	Correct	263 ms	17764 KB	Output is correct
6	Correct	263 ms	17844 KB	Output is correct
7	Correct	237 ms	17768 KB	Output is correct
8	Correct	240 ms	17764 KB	Output is correct
9	Correct	107 ms	15844 KB	Output is correct
10	Correct	348 ms	17872 KB	Output is correct

Subtask #3
0 / 45.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	35 ms	1520 KB	Output is correct
3	Correct	35 ms	1548 KB	Output is correct
4	Correct	36 ms	1520 KB	Output is correct
5	Correct	36 ms	1520 KB	Output is correct
6	Correct	36 ms	1516 KB	Output is correct
7	Correct	27 ms	1644 KB	Output is correct
8	Correct	31 ms	1520 KB	Output is correct
9	Correct	21 ms	1780 KB	Output is correct
10	Correct	100 ms	4836 KB	Output is correct
11	Correct	155 ms	15724 KB	Output is correct
12	Correct	255 ms	17736 KB	Output is correct
13	Correct	263 ms	17764 KB	Output is correct
14	Correct	263 ms	17844 KB	Output is correct
15	Correct	237 ms	17768 KB	Output is correct
16	Correct	240 ms	17764 KB	Output is correct
17	Correct	107 ms	15844 KB	Output is correct
18	Correct	348 ms	17872 KB	Output is correct
19	Incorrect	245 ms	19488 KB	Output isn't correct
20	Halted	0 ms	0 KB	-

답안 #95452

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 45.0 / 45.0

Subtask #3 0 / 45.0

Subtask #1
10.0 / 10.0

Subtask #2
45.0 / 45.0

Subtask #3
0 / 45.0