【Bzoj3932】【Luogu3168】任务查询系统

来源和评测点

CQOI2015
Bzoj3932
Luogu3168

题目

【题目大意】
电脑有n个任务需要执行,任务i在si到ei时正在工作,优先级为p
给m个询问,每个询问给出一个时间点xi和一个数ki。
问在xi这个时间点时,所有正在工作的任务中优先级从小到大排列,前ki个的优先级之和是多少
【输入格式】
输入文件第一行包含两个空格分开的正整数m和n,分别表示任务总数和时间范围。
接下来m行,每行包含三个空格分开的正整数Si、Ei和Pi(Si<=Ei),描述一个任务。
接下来n行,每行包含四个空格分开的整数Xi、Ai、Bi和Ci,描述一次查询。
查询的参数Ki需要由公式 Ki=1+(Ai*Pre+Bi) mod Ci计算得到。
其中Pre表示上一次查询的结果,对于第一次查询,Pre=1。

1<=m,n,Si,Ei,Ci<=100000,
0<=Ai,Bi<=100000,1<=Pi<=10000000,Xi为1到n的一个排列
【输出格式】
输出共n行,每行一个整数,表示查询结果。
【输入样例】
4 3
1 2 6
2 3 3
1 3 2
3 3 4
3 1 3 2
1 1 3 4
2 2 4 3
【输出样例】
2
8
11

刷题记录

分析

把每一秒看作一个操作来可持续化
好吧其实就是有着权值线段树的前缀和

然鹅,这题居然不卡暴力……
基于【面向数据编程】和【以题目为导向】,暂时就不写正解了,精A飘过

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
//Zory-2018
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
int mymin(int x,int y) {return x<y?x:y;}
int mymax(int x,int y) {return x>y?x:y;}
int qread1(void)
{
char c=getchar();int d=0;
while(c<'0' or c>'9') c=getchar();
while(c>='0' and c<='9') d=d*10+c-'0',c=getchar();
return d;
}
ll qread2(void)
{
char c=getchar();ll d=0;
while(c<'0' or c>'9') c=getchar();
while(c>='0' and c<='9') d=d*10+c-'0',c=getchar();
return d;
}
//*******************全局常量*******************
const int MAXN=110000;
//*******************全局定义*******************
struct nod
{
int a,b;
ll c;
}p[MAXN];
bool operator < (nod x,nod y)
{
return x.c<y.c;
}
//*******************实现*******************
//*******************主函数*******************
int main()
{
int m,n;scanf("%d%d",&m,&n);
for(int i=1;i<=m;i++) p[i].a=qread1(),p[i].b=qread1(),p[i].c=qread2();
sort(p+1,p+1+m);
ll pre=1;
for(int i=1;i<=n;i++)
{
int x=qread1();ll a=qread2(),b=qread2(),c=qread2();
ll k=1+(a*pre+b)%c;pre=0;
for(int i=1,j=0;i<=m and j<k;i++)
if(p[i].a<=x and x<=p[i].b)
pre+=p[i].c,j++;
printf("%lld\n",pre);
}
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/9028.html
转载请注明出处,谢谢!