【HDOJ】4553 约会安排
2024-10-16 08:44:32
线段树。线段树的细节很重要，小数据遍历可以发现问题。
/* 4553 */
#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <cctype>
#include <cassert>
#include <functional>
#include <iterator>
#include <iomanip>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,1024000") #define sti set<int>
#define stpii set<pair<int, int> >
#define mpii map<int,int>
#define vi vector<int>
#define pii pair<int,int>
#define vpii vector<pair<int,int> >
#define rep(i, a, n) for (int i=a;i<n;++i)
#define per(i, a, n) for (int i=n-1;i>=a;--i)
#define clr clear
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1 typedef struct {
int l, r;
int nls, nrs, nms;
int dls, drs, dms;
} node_t; const int study = ;
const int ds = ;
const int ns = ;
const int maxn = 1e5+;
node_t nd[maxn<<]; void Build(int l, int r, int rt) {
nd[rt].l = l;
nd[rt].r = r;
nd[rt].nls = nd[rt].nrs = nd[rt].nms = r-l+;
nd[rt].dls = nd[rt].drs = nd[rt].dms = r-l+;
if (l == r)
return ; int mid = (l + r) >> ;
Build(lson);
Build(rson);
} void PushDown(int rt) {
int l = nd[rt].l, r = nd[rt].r;
if (l == r) return ;
int lb = rt<<;
int rb = lb |;
int mid = (l + r) >> ; if (nd[rt].dms == ) {
nd[lb].dls = nd[lb].drs = nd[lb].dms = ;
nd[rb].dls = nd[rb].drs = nd[rb].dms = ;
} else if (nd[rt].dms == r-l+) {
nd[lb].dls = nd[lb].drs = nd[lb].dms = mid - l + ;
nd[rb].dls = nd[rb].drs = nd[rb].dms = r - mid;
} if (nd[rt].nms == ) {
nd[lb].nls = nd[lb].nrs = nd[lb].nms = ;
nd[rb].nls = nd[rb].nrs = nd[rb].nms = ;
} else if (nd[rt].nms == r-l+) {
nd[lb].nls = nd[lb].nrs = nd[lb].nms = mid - l + ;
nd[rb].nls = nd[rb].nrs = nd[rb].nms = r - mid;
}
} void PushUp1(int rt) {
int l = nd[rt].l, r = nd[rt].r;
if (l == r) return ;
int lb = rt<<;
int rb = lb |;
int mid = (l + r) >> ; nd[rt].dls = nd[lb].dls;
nd[rt].drs = nd[rb].drs;
nd[rt].dms = max(nd[lb].dms, nd[rb].dms);
nd[rt].dms = max(nd[rt].dms, nd[lb].drs+nd[rb].dls); if (nd[lb].dls == mid - l + )
nd[rt].dls += nd[rb].dls;
if (nd[rb].drs == r - mid)
nd[rt].drs += nd[lb].drs;
} void PushUp2(int rt) {
int l = nd[rt].l, r = nd[rt].r;
if (l == r) return ;
int lb = rt<<;
int rb = lb |;
int mid = (l + r) >> ; nd[rt].nls = nd[lb].nls;
nd[rt].nrs = nd[rb].nrs;
nd[rt].nms = max(nd[lb].nms, nd[rb].nms);
nd[rt].nms = max(nd[rt].nms, nd[lb].nrs+nd[rb].nls); if (nd[lb].nls == mid - l + )
nd[rt].nls += nd[rb].nls;
if (nd[rb].nrs == r - mid)
nd[rt].nrs += nd[lb].nrs;
} int query1(int qt, int rt) {
PushDown(rt); if (nd[rt].dms < qt)
return ; if (nd[rt].dls >= qt)
return nd[rt].l; if (nd[rt<<].dms >= qt)
return query1(qt, rt<<); if (nd[rt<<].drs + nd[rt<<|].dls >= qt)
return nd[rt<<].r - nd[rt<<].drs + ; return query1(qt, rt<<|);
} int query2(int qt, int rt) {
PushDown(rt); if (nd[rt].nms < qt)
return ; if (nd[rt].nls >= qt)
return nd[rt].l; if (nd[rt<<].nms >= qt)
return query2(qt, rt<<); if (nd[rt<<].nrs + nd[rt<<|].nls >= qt)
return nd[rt<<].r - nd[rt<<].nrs + ; return query2(qt, rt<<|);
} void update0(int L, int R, int rt) {
if (L<=nd[rt].l && nd[rt].r<=R) {
nd[rt].nls = nd[rt].nrs = nd[rt].nms = nd[rt].r-nd[rt].l+;
nd[rt].dls = nd[rt].drs = nd[rt].dms = nd[rt].r-nd[rt].l+;
return ;
} PushDown(rt);
int mid = (nd[rt].l + nd[rt].r) >> ; if (mid >= R) {
update0(L, R, rt<<);
} else if (mid < L) {
update0(L, R, rt<<|);
} else {
update0(L, R, rt<<);
update0(L, R, rt<<|);
} PushUp1(rt);
PushUp2(rt);
} void update1(int L, int R, int rt) {
if (L<=nd[rt].l && nd[rt].r<=R) {
nd[rt].dls = nd[rt].drs = nd[rt].dms = ;
return ;
} PushDown(rt);
int mid = (nd[rt].l + nd[rt].r) >> ; if (mid >= R) {
update1(L, R, rt<<);
} else if (mid < L) {
update1(L, R, rt<<|);
} else {
update1(L, R, rt<<);
update1(L, R, rt<<|);
} PushUp1(rt);
} void update2(int L, int R, int rt) {
if (L<=nd[rt].l && nd[rt].r<=R) {
nd[rt].nls = nd[rt].nrs = nd[rt].nms = ;
nd[rt].dls = nd[rt].drs = nd[rt].dms = ;
return ;
} PushDown(rt);
int mid = (nd[rt].l + nd[rt].r) >> ; if (mid >= R) {
update2(L, R, rt<<);
} else if (mid < L) {
update2(L, R, rt<<|);
} else {
update2(L, R, rt<<);
update2(L, R, rt<<|);
} PushUp1(rt);
PushUp2(rt);
} int main() {
ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif int t;
int n, q;
int qt, l, r, ans;
char cmd[]; scanf("%d", &t);
rep(tt, , t+) {
scanf("%d %d", &n, &q);
Build(, n, );
printf("Case %d:\n", tt);
while (q--) {
scanf("%s", cmd);
if (cmd[] == 'S') {
scanf("%d %d", &l, &r);
update0(l, r, );
puts("I am the hope of chinese chengxuyuan!!");
} else if (cmd[] == 'D') {
scanf("%d", &qt);
l = query1(qt, );
if (l == ) {
puts("fly with yourself");
} else {
printf("%d,let's fly\n", l);
update1(l, l+qt-, );
}
} else if (cmd[] == 'N') {
scanf("%d", &qt);
l = query1(qt, );
if (l == )
l = query2(qt, );
if (l == ) {
puts("wait for me");
} else {
printf("%d,don't put my gezi\n", l);
update2(l, l+qt-, );
}
}
}
} #ifndef ONLINE_JUDGE
printf("time = %d.\n", (int)clock());
#endif return ;
}
最新文章
- 虚拟机VMware 12 Pro 永久许可证激活密钥
- SAP打印机配置
- cf219d
- 用sql从一张表更新数据到另外一张表(多表数据迁移)
- JavaScript 高性能笔记
- nested exception is org.xml.sax.SAXParseException; lineNumber: 8; columnNumber: 56; cvc-complex-type.2.4.c通配符的匹配很全面, 但无法找到元素 'dubbo:application' 的声明
- hdu 4289 最大流拆点
- CSS子元素margin-top对于父元素的影响
- OpenJudge计算概论-寻找下标
- AES CBC 128的实现
- php 双向队列类
- jQuery 学习笔记（三）——事件与应用
- ORA-00379 缓冲池 DEFAULT 中无法提供 32K 块大小的空闲缓冲区
- windows server 2008 R2 禁用ipv6和隧道适配器
- Flutter 页面入栈和出栈
- Condtion type Z123 is mandatory!
- php curl参数详解之post方法
- android studio 包名冲突解决
- linux判断文件大小
- 解决WDCP3环境gbk网站编码程序乱码问题