原题传送门:P1204 [USACO1.2]挤牛奶Milking Cows
实际是道很弱智的题目qaq
但窝还是觉得用珂朵莉树写会++rp(窝都初二了,还要考pj)
前置芝士:珂朵莉树
窝博客里对珂朵莉树的介绍
没什么好说的自己看看吧
每个农夫就assign_val一下,但要注意一下细节qaq
窝不会告诉你因这个错调了我十几分钟qaq
应该写assign_val(l,r-1,1),查询时应写query(lmin,rmax,1/0)
其他没什么好说的了,细节详见程序
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define IT set<node>::iterator
using namespace std;
struct IO_Tp
{
static const int _I_Buffer_Size = 1 << 24;
char _I_Buffer[_I_Buffer_Size];
char* _I_pos;
static const int _O_Buffer_Size = 1 << 24;
char _O_Buffer[_O_Buffer_Size];
char* _O_pos;
IO_Tp() : _I_pos(_I_Buffer), _O_pos(_O_Buffer)
{
fread(_I_Buffer, 1, _I_Buffer_Size, stdin);
}
~IO_Tp()
{
fwrite(_O_Buffer, 1, _O_pos - _O_Buffer, stdout);
}
inline bool is_digit(const char ch)
{
return '0' <= ch && ch <= '9';
}
inline IO_Tp& operator>>(int& res)
{
res = 0;
while (!is_digit(*_I_pos))
++_I_pos;
do
(res *= 10) += (*_I_pos++) & 15;
while (is_digit(*_I_pos));
return *this;
}
inline IO_Tp& operator<<(int n)
{
static char _buf[10];
char* _pos(_buf);
do
*_pos++ = '0' + n % 10;
while (n /= 10);
while (_pos != _buf)
*_O_pos++ = *--_pos;
return *this;
}
inline IO_Tp& operator<<(char ch)
{
*_O_pos++ = ch;
return *this;
}
} IO;
inline int Max(register int a,register int b)
{
return a>b?a:b;
}
inline int Min(register int a,register int b)
{
return a<b?a:b;
}
struct node
{
int l,r;
mutable bool v;
node(int L, int R=-1, bool V=0):l(L), r(R), v(V) {}
bool operator<(const node& o) const
{
return l < o.l;
}
};
set<node> s;
IT split(int pos)
{
IT it = s.lower_bound(node(pos));
if (it != s.end() && it->l == pos)
return it;
--it;
int L = it->l, R = it->r;
bool V = it->v;
s.erase(it);
s.insert(node(L, pos-1, V));
return s.insert(node(pos, R, V)).first;
}
void assign_val(int l,int r,bool v)
{
IT itr = split(r+1),itl = split(l);
s.erase(itl, itr);
s.insert(node(l, r, v));
}
inline int query(register int l,register int r,register bool v)
{
int sum=0,res=0;
IT itr = split(r+1),itl = split(l);
for(;itl!=itr;++itl)
if(itl->v==v)
sum+=itl->r-itl->l+1;
else
{
res=Max(res,sum);
sum=0;
}
return res;
}
int main()
{
int n;
IO>>n;
int a=1000005,b=0;
s.insert(node(0,1000005));
while(n--)
{
int l,r;
IO>>l>>r;
assign_val(l,r-1,1);
a=Min(a,l);
b=Max(b,r);
}
IO<<query(a,b,1)<<' '<<query(a,b,0);
return 0;
}
【题解】Luogu P1204 [USACO1.2]挤牛奶Milking Cows的更多相关文章
-
洛谷P1204 [USACO1.2]挤牛奶Milking Cows
P1204 [USACO1.2]挤牛奶Milking Cows 474通过 1.4K提交 题目提供者该用户不存在 标签USACO 难度普及- 提交 讨论 题解 最新讨论 请各位帮忙看下程序 错误 ...
-
P1204 [USACO1.2]挤牛奶Milking Cows
题目描述 三个农民每天清晨5点起床,然后去牛棚给3头牛挤奶.第一个农民在300秒(从5点开始计时)给他的牛挤奶,一直到1000秒.第二个农民在700秒开始,在 1200秒结束.第三个农民在1500秒开 ...
-
洛谷—— P1204 [USACO1.2]挤牛奶Milking Cows
https://www.luogu.org/problem/show?pid=1204 题目描述 三个农民每天清晨5点起床,然后去牛棚给3头牛挤奶.第一个农民在300秒(从5点开始计时)给他的牛挤奶, ...
-
洛谷 P1204 [USACO1.2]挤牛奶Milking Cows Label:模拟Ex 74分待查
题目描述 三个农民每天清晨5点起床,然后去牛棚给3头牛挤奶.第一个农民在300秒(从5点开始计时)给他的牛挤奶,一直到1000秒.第二个农民在700秒开始,在 1200秒结束.第三个农民在1500秒开 ...
-
洛谷 P1204 [USACO1.2]挤牛奶Milking Cows
题目描述 三个农民每天清晨5点起床,然后去牛棚给3头牛挤奶.第一个农民在300秒(从5点开始计时)给他的牛挤奶,一直到1000秒.第二个农民在700秒开始,在 1200秒结束.第三个农民在1500秒开 ...
-
[USACO1.2]挤牛奶Milking Cows
题目描述 三个农民每天清晨5点起床,然后去牛棚给3头牛挤奶.第一个农民在300秒(从5点开始计时)给他的牛挤奶,一直到1000秒.第二个农民在700秒开始,在 1200秒结束.第三个农民在1500秒开 ...
-
【洛谷P1204】【USACO1.2】挤牛奶Milking Cows
P1204 [USACO1.2]挤牛奶Milking Cows 题目描述 三个农民每天清晨5点起床,然后去牛棚给3头牛挤奶.第一个农民在300秒(从5点开始计时)给他的牛挤奶,一直到1000秒.第二个 ...
-
USACO Training Section 1.2 挤牛奶Milking Cows
题目描述 三个农民每天清晨5点起床,然后去牛棚给3头牛挤奶.第一个农民在300秒(从5点开始计时)给他的牛挤奶,一直到1000秒.第二个农民在700秒开始,在 1200秒结束.第三个农民在1500秒开 ...
-
题解 P1208 【[USACO1.3]混合牛奶 Mixing Milk】
其实根本没有一楼dalao描述的那么麻烦...... 一楼dalao其实吧,采用了一种纯属模拟的方式. 下面是我的*思想 但是一个个地做减法是不是太慢了?(*思想) 于是我们是不是可以直接进行 ...
随机推荐
-
Navicat for mysql 远程连接 mySql数据库10061、1045错误
原文地址:http://www.111cn.net/database/mysql/46377.htm 有朋友可能会碰到使用Navicat for mysql 远程连接 mySql数据库会提示10061 ...
-
IE的@cc_on条件编译
1: alert("浏览器版本为:"+sSuffix) 用来判断浏览器的版本很好用 var b = /*@cc_on!@*/false; 其中/*@cc_on ..... @*/之 ...
-
Struct 和 Union 的详细区别
Union: 共用体 Struct:结构体 两者的区别: 1:共用体和结构体都是由多个不同的数据类型成员组成, 但在任何同一时刻, 共用体只存放一个被选中的成员, 而结构体则存放所有的成员变量. 2: ...
-
linux 硬盘
df -hT 查看格式 各种文件 mount命令 可以挂载那些块设备:光盘.磁盘分区.U盘 光盘:文件系统:iso9660 iso文件文件系统:iso9660 iso文件可以进行挂载的 mount c ...
-
【angularjs】使用angularjs模拟淘宝首页-淘宝头条滚动效果
<!DOCTYPE html> <html> <head> <meta charset="UTF-8"> <title> ...
-
centos6.5环境基于corosync+cman+rgmanager实现RHCS及iscsi+gfs2+clvm的文件系统集群
centos6.5环境基于corosync+cman+rgmanager实现RHCS及iscsi+gfs2+clvm文件系统集群 一.环境准备 服务器列表: ansible server : 192. ...
-
jQuery基础(1)
一.jQuery的介绍 1.为什么要使用jQuery? 在用js写代码时,会遇到一些问题,如下: 1)window.onload 事件有事件覆盖的问题,因此只能写一个事件: 2)代码容错性差: 3)浏 ...
-
Ajax与XMLHttpRequest随笔
1.XMLHttpRequest对象 创建XHR对象:let xhr = new XMLHttpRequest(); open():启动一个请求准备发送 open()接收3个参数:请求类型('GET' ...
-
.NET设计模式(4):建造者模式(Builder Pattern)(转载)
概述 在 软件系统中,有时候面临着“一个复杂对象”的创建工作,其通常由各个部分的子对象用一定的算法构成:由于需求的变化,这个复杂对象的各个部分经常面临着剧 烈的变化,但是将它们组合在一起的算法确相对稳 ...
-
Knight Moves(广搜BFS)
Description A friend of you is doing research on the Traveling Knight Problem (TKP) where you are to ...