[2015 - 2016 ACM - ICPC, NEERC, Southern Subregional Contest G] [데이터 구조 - 선분 수] 채용 준비 시간 완료 시간 최초 완료 날짜
6421 단어 선분 수ACMICPCcodeforces
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output
The head of human resources department decided to hire a new employee. He created a test exercise for candidates which should be accomplished in at most m working days. Each candidate has to pass this test exercise. During the j-th day a candidate is allowed to be in the office for at most tj units of time.
Overall, n candidates decided to apply for the job and sent out their resumes. Based on data received the head has defined two parameters describing every candidate: di and ri. The parameter di is the time to get prepared for work which the i-th candidate spends each morning. This time doesn't depend on day. The parameter ri is the total working time needed for the i-th candidate to accomplish the whole test exercise.
Thus the time spent in the office in the j-th day consists of di units of time to get prepared and some units of time to proceed with the exercise. A candidate can skip entire working day and do not come to the office. Obviously in this case he doesn't spend di units of time to prepare.
To complete the exercise a candidate should spend exactly ri units of time working on the exercise (time to prepare is not counted here).
Find out for each candidate what is the earliest possible day when he can fully accomplish the test exercise. It is allowed to skip working days, but if candidate works during a day then he must spend di units of time to prepare for work before he starts progressing on the exercise.
Input
The first line contains two integer numbers n, m (1 ≤ n, m ≤ 2·105) — the number of candidates and the maximum number of working days to do the test exercise.
The second line contains m integer numbers t1, t2, ..., tm (1 ≤ tj ≤ 106) — the durations of working days in time units.
The following n lines contain two integers each: di, ri (0 ≤ di ≤ 106, 1 ≤ ri ≤ 106) — how much time in the beginning of a day is required for i-th candidate before he starts his work on the test exercise and how much time it is needed for him to accomplish this task.
Output
Output a sequence of n integer numbers b1, b2, ..., bn, where bi is the earliest day when the i-th candidate can finish the test exercise.
In case the i-th candidate cannot finish the test exercise in m days output bi = 0.
Days in this problem are numbered from 1 to m in the order they are given in the input.
Sample test(s)
input
3 3
4 2 5
1 3
2 5
3 4
output
1 3 0
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<ctype.h>
#include<vector>
#include<map>
#include<algorithm>
#define ls o<<1
#define rs o<<1|1
using namespace std;
typedef long long LL;
const int N=2e5+10;
int n,m;
int W,V,O;
int ans[N];
struct A
{
int l,r,flag,num,min;
LL sum;
}a[1<<19];
struct B
{
int w,v,o;
bool operator < (const B& b)const
{
return w<b.w;
}
}b[N];
void pushup(int o)
{
a[o].sum=a[ls].sum+a[rs].sum;
a[o].num=a[ls].num+a[rs].num;
a[o].min=min(a[ls].min,a[rs].min);
}
void pushdown(int o)
{
if(a[o].flag)
{
a[ls].sum-=(LL)a[ls].num*a[o].flag;
a[rs].sum-=(LL)a[rs].num*a[o].flag;
a[ls].flag+=a[o].flag;
a[rs].flag+=a[o].flag;
a[ls].min-=a[o].flag;
a[rs].min-=a[o].flag;
a[o].flag=0;
return;
}
}
void build(int o,int l,int r)
{
a[o].l=l;
a[o].r=r;
a[o].flag=0;
if(a[o].l==a[o].r)
{
scanf("%d",&a[o].sum);
a[o].num=1;
a[o].min=a[o].sum;
return;
}
int m=(a[o].l+a[o].r)>>1;
build(ls,l,m);
build(rs,m+1,r);
pushup(o);
}
void del(int o)
{
if(a[o].l==a[o].r)
{
a[o].sum=0;
a[o].num=0;
a[o].min=1e9;
return;
}
pushdown(o);
if(a[ls].min<=0)del(ls);
if(a[rs].min<=0)del(rs);
pushup(o);
}
void change(int o,int l,int r)
{
if(l==a[o].l&&r==a[o].r)
{
a[o].sum-=(LL)W*a[o].num;
a[o].flag+=W;
a[o].min-=W;
if(a[o].min<=0)del(o);// num
return;
}
pushdown(o);
int m=(a[o].l+a[o].r)>>1;
if(r<=m)change(ls,l,r);
else if(l>m)change(rs,l,r);
else
{
change(ls,l,m);
change(rs,m+1,r);
}
pushup(o);
}
void find(int o)
{
if(a[o].l==a[o].r)
{
ans[O]=a[o].l;
return;
}
pushdown(o);
if(a[ls].sum>=V)find(ls);
else
{
V-=a[ls].sum;//
find(rs);
}
pushup(o);
}
int main()
{
while(~scanf("%d%d",&m,&n))
{
build(1,1,n);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&b[i].w,&b[i].v);
b[i].o=i;
}
sort(b+1,b+m+1);
for(int i=1;i<=m;i++)
{
W=b[i].w-b[i-1].w;
if(W)change(1,1,n);
V=b[i].v;
O=b[i].o;
if(a[1].sum<V)ans[O]=0;
else find(1);
}
for(int i=1;i<=m;i++)printf("%d ",ans[i]);puts("");
}
return 0;
}
/*
【trick&& 】
1, , int。
2, , 。
【 】
n(2e5) , 。
m(2e5) , , ( A, B) pair,() 1e6
, , A。
, , , 。
( >0) >= B, 。
( , 0)
【 】
-
【 】
?
, ——∑( - ), <=0 , >=
, , , ——
, ——
1, ,
2, , 。
3, , , , 。
4, , , , 。
——
?
1, 。
2, —— sum
3,
, , ?
? ——
1, num , sum-=num*W
2, 。
2, sum 。
num, num
——
1,sum-=num*W
2, 。 <=0, , pushup 。
pushup() pushdown() 。
——
1,flag pushdown()
2, , ,flag 。
: sum, flag, min,
【 && 】
, O((n+m)logn)
*/
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
HDU - 1166 - 적병 포진 (나무형 수조 또는 선분 수)C 국 의 앙 숙 A 국 은 그동안 군사훈련 을 하고 있 었 기 때문에 C 국 간첩 두목 인 데 릭 과 그의 수하 인 티 디 는 또 바 빠 지기 시작 했다.A 국 가 는 해안선 을 따라 직선 으로 N 개 공병 캠프 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.