正文

ural1424minibus

mxzf0213  mxzf0213  2022-08-04  575

关键词：

Minibus

Time limit: 1.0 second
Memory limit: 64 MB

Background

Minibus driver Sergey A. Greedson has become totally famous for his phenomenal greediness. He claimed time and again that he held himself in readiness to throttle his brother and sell out all friends for an extra cent. Unfortunately, these statements were impossible to verify because Sergey had got neither brothers nor friends, home or family. And he had not got any money either. An old minibus seemed to be the only property of Mr. Greedson. So he traveled the city giving occasional passengers a lift and sometimes examining pavements for dumps...

One day the heavens took pity on Sergey and decided to stop his useless being in out cruel world. For this noble purpose an axe fell down on the head of carefree Mr. Greedson, who had just left the minibus on account of inviting shine of an empty beer bottle. The dreams of profitable bottle sale went out of his head in a blink replaced by the axe. In a figurative sense, of course. Heavens tool could not break a stiff skull of Mr. Greedson but, as it turned out later, gave him several rather useful abilities.

Soon after the axe was sold, Sergey discovered his ability to foresee the future. What a scope, what a prospect was given to the artless minibus driver! Who are we and where are we going? What is to be feared and hoped? The answers for these questions did not worry Mr. Greedson at all. But Sergey‘s greedy mind was clever enough to use his new ability to earn some money. As many others, Mr. Greedson was absolutely sure that the easiest way to enrichment was to fleece working-people, in other words, the passengers of his own minibus.

Problem

Every day the minibus makes a passage from 1-st to N-th bus stop. There are M passenger seats in the minibus. Once in the evening Mr. Greedson has counted the probability lines and found out that the next day K persons would wait for the minibus on the bus stops. For each person the number of bus stop S[i], where he wants to get into the minibus, and the number of bus stop F[i], where he is going to leave the minibus, were found. According to Sergey‘s pricing policy, each passenger must pay P dollars for a ticket despite the number of passed bus stops. More over, at a bus stop Mr. Greedson may allow some persons to get into the minibus and ban others (in other words, he may choose his passengers himself). After the problem was posed to maximize the gain, Sergey decided to find the persons who should be allowed to get into the minibus. Unfortunately, he does not possess enough power to perform it. And what about you?

Input

The first line contains integer numbers N (2 ≤ N ≤ 100000), M (1 ≤ M ≤ 1000), K (0 ≤ K ≤ 50000) and P (1 ≤ P ≤ 10000). Each of the next K lines contains the integer numbers S[i] and F[i] (1 ≤ S[i] < F[i] ≤ N) for the corresponding passenger.

Output

The first line should contain the maximal gain. The second line should contain the numbers of persons, who should be allowed to get into the minibus to obtain this gain. The numbers should be listed in any order and separated by single spaces. If the problem has several solutions, you should output any of them.

Sample

input	output
6 2 6 9 1 4 2 6 1 5 2 3 4 6 3 6	36 1 5 6 4

input

output

36
1 5 6 4

分析：贪心+线段树；

　　　按结束时间排序，则尽可能让座位坐满，线段树区间更新判断是否可坐；

代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define rep(i,m,n) for(i=m;i<=n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
#define mod 1000000007
#define inf 0x3f3f3f3f
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ll long long
#define pi acos(-1.0)
#define pii pair<int,int>
#define Lson L, mid, rt<<1
#define Rson mid+1, R, rt<<1|1
const int maxn=1e5+10;
using namespace std;
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}
int n,m,k,t;
vi ans;
struct node
{
    int x,y,id;
    bool operator<(const node&p)const
    {
        return y<p.y;
    }
}a[maxn];
struct Node
{
    int  Max, lazy;
} T[maxn<<2];

void PushUp(int rt)
{
    T[rt].Max = max(T[rt<<1].Max, T[rt<<1|1].Max);
}

void PushDown(int L, int R, int rt)
{
    int mid = (L + R) >> 1;
    int t = T[rt].lazy;
    T[rt<<1].Max += t;
    T[rt<<1|1].Max += t;
    T[rt<<1].lazy += t;
    T[rt<<1|1].lazy += t;
    T[rt].lazy = 0;
}

void Update(int l, int r, int v, int L, int R, int rt)
{
    if(l==L && r==R)
    {
        T[rt].lazy += v;
        T[rt].Max += v;
        return ;
    }
    int mid = (L + R) >> 1;
    if(T[rt].lazy) PushDown(L, R, rt);
    if(r <= mid) Update(l, r, v, Lson);
    else if(l > mid) Update(l, r, v, Rson);
    else
    {
        Update(l, mid, v, Lson);
        Update(mid+1, r, v, Rson);
    }
    PushUp(rt);
}

int Query(int l, int r, int L, int R, int rt)
{
    if(l==L && r== R)
    {
        return T[rt].Max;
    }
    int mid = (L + R) >> 1;
    if(T[rt].lazy) PushDown(L, R, rt);
    if(r <= mid) return Query(l, r, Lson);
    else if(l > mid) return Query(l, r, Rson);
    return max(Query(l, mid, Lson) , Query(mid + 1, r, Rson));
}
int main()
{
    int i,j;
    scanf("%d%d%d%d",&n,&m,&k,&t);
    rep(i,1,k)scanf("%d%d",&a[i].x,&a[i].y),a[i].id=i;
    sort(a+1,a+k+1);
    rep(i,1,k)
    {
        if(Query(a[i].x,a[i].y-1,1,n,1)<m)
        {
            ans.pb(a[i].id);
            Update(a[i].x,a[i].y-1,1,1,n,1);
        }
    }
    printf("%lld
",(ll)ans.size()*t);
    if(ans.size())printf("%d",ans[0]);
    for(i=1;i<ans.size();i++)printf(" %d",ans[i]);
    printf("
");
    //system("Pause");
    return 0;
}

1424：例题3喷水装置(代码片段)

1424：【例题3】喷水装置题解所以就可以吧这些圆简化为线段思路①读入数据,并计算a[cnt].s=p-sqrt((r*r)-(w/2.0)*(w/2.0)); 查看详情

c_cppuva1424-推销员(代码片段)

查看详情

g-excel排序hdu1424

G - EXCEL排序TimeLimit: 2000/1000 MS(Java/Others) MemoryLimit: 128000/64000 KB(Java/Others)Submit StatusProblemDescriptionExcel可以对一组纪录按任意指查看详情

好吧，我有一个关于 MySql 中的递归的问题，关于创建递归阶乘函数。它给了我错误1424：

...中的递归的问题，关于创建递归阶乘函数。它给了我错误1424：【英文标题】：Well,IhaveaproblemaboutrecursioninMySql,aboutcreatingarecursivefactorialfunction.itgivesmeerror1424:【发布时间】：2022-01-0422:20:18【问题描述】：DELIMITER//createfunctionFactorialR( 查看详情

leetcode1424.diagonaltraverseii(代码片段)

文章作者：Tyan博客：noahsnail.com | CSDN | 简书1.Description2.Solution**解析：**Version1，根据矩阵对角线元素的规律，行坐标与列坐标和相等的元素属于同一对角线，由于对角线从左下到右上，因此应该同一... 查看详情

51nod1424零树(代码片段)

Discription有一棵以1为根的树，他有n个结点，用1到n编号。第i号点有一个值vi。现在可以对树进行如下操作：步骤1：在树中选一个连通块，这个连通块必须包含1这个结点。步骤2：然后对这个连通块中所有结点的值加1或者减1。问... 查看详情

ural-1901spaceelevators

题目：NowadaysspaceshipsareneverlaunchedfromtheEarth‘ssurface.ThereisahugespaceportplacedinthegeostationaryorbitandconnectedtotheEarthwithcarbonnanotubecables.Peopleandcargoaredeliveredtotheorbitbyelevat 查看详情

ural2089experiencedcoachtwosat

DescriptionMishatrainsseveralACMteamsattheuniversity.Heisanexperiencedcoach,andhedoesnotunderestimatethemeaningoffriendlyandcollaborativeatmosphereduringtrainingsessions.Itusedtobethatway,butoneofthet 查看详情

ural2020trafficjaminflowertown

2020.TrafficJaminFlowerTownTimelimit:1.0secondMemorylimit:64MBHavingreturnedfromSunCity,Dunnotoldallhisfriendsthateveryshortymayhaveapersonalautomobile.Immediatelyafterthatsomanycitizenstookafancyofbe 查看详情

ural1855tradeguildsoferathia

TradeGuildsofErathiaTimelimit:2.0secondMemorylimit:64MBThecontinentofAntagarichwascolonizedslowly.LongagoitsnorthernpartwasinhabitedbytheelvesofAvlee.Later,thehotsoutherndesertofBracadawasoccupiedbyth 查看详情

ural2016magicandscience

2016.MagicandScienceTimelimit:1.0secondMemorylimit:64MBScientistswhospecializeinwitchcrafthaverecentlydiscoveredanewelementaryparticlecalledamagion.Studyingthelawsofmagions’movement,agroupofthre 查看详情

ural2021scarilyinteresting!

2021.Scarilyinteresting!Timelimit:1.0secondMemorylimit:64MBThisyearatMonstersUniversityitisdecidedtoarrangeScareGames.AttheGamesallcampusgathersatthestadiumstands,andtheScareprogramstudentsdivideintot 查看详情

[ural1519]formula1

[URAL1519]Formula1试题描述Regardlessofthefact,thatVologdacouldnotgetrightstoholdtheWinterOlympicgamesof20**,itiswell-known,thatthecitywillconductoneoftheFormula1events.Surely,forsuchanimportantthinganewra 查看详情

tyvj1424-占卜diy(代码片段)

题目有点长，对于样例最好拿张A4纸模拟写一遍。可以发现程序一定不会死循环，因为每种牌都是4张，而死循环的条件是某种牌有5张然后你拿了又放进去。如果写出来死循环了，那就是写不对了。有几点可能是需要注意的：1.A... 查看详情

ural1118.nontrivialnumbers

1118.NontrivialNumbersTimelimit:2.0secondMemorylimit:64MB SpecialistsofSKBKonturhavedevelopedauniquecryptographicalgorithmforneedsofinformationprotectionwhiletransmittingdataovertheInternet.Thema 查看详情

ural2015zhenyamovesfromthedormitory

2015.ZhenyamovesfromthedormitoryTimelimit:1.0secondMemorylimit:64MBAftermovingfromhisparents’placeZhenyahasbeenlivingintheUniversitydormitoryforamonth.However,hegotprettytiredofthecurfewtimeandq 查看详情

ural2017bestofabadlot

2017.BestofabadlotTimelimit:1.0secondMemorylimit:64MBAcruiselinerhasn’tmovedawayfromthelandevenforthreemileswhenitbecameapparentthatsomebodyhasdrownedoneofthestewardsintheswimmingpool.Thecaptain 查看详情

ural2012aboutgrishan.

2012.AboutGrishaN.Timelimit:1.0secondMemorylimit:64MBGrishaN.toldhistwoteammatesthathewasgoingtosolveallgivenproblemsatthesubregionalcontest,eveniftheteammateswouldn’tshowupatthecompetition.Thet 查看详情