【题解】Luogu P1204 [USACO1.2]挤牛奶Milking Cows

时间:2022-04-13 22:28:31

原题传送门: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的更多相关文章

  1. 洛谷P1204 &lbrack;USACO1&period;2&rsqb;挤牛奶Milking Cows

    P1204 [USACO1.2]挤牛奶Milking Cows 474通过 1.4K提交 题目提供者该用户不存在 标签USACO 难度普及- 提交  讨论  题解 最新讨论 请各位帮忙看下程序 错误 ...

  2. P1204 &lbrack;USACO1&period;2&rsqb;挤牛奶Milking Cows

    题目描述 三个农民每天清晨5点起床,然后去牛棚给3头牛挤奶.第一个农民在300秒(从5点开始计时)给他的牛挤奶,一直到1000秒.第二个农民在700秒开始,在 1200秒结束.第三个农民在1500秒开 ...

  3. 洛谷—— P1204 &lbrack;USACO1&period;2&rsqb;挤牛奶Milking Cows

    https://www.luogu.org/problem/show?pid=1204 题目描述 三个农民每天清晨5点起床,然后去牛棚给3头牛挤奶.第一个农民在300秒(从5点开始计时)给他的牛挤奶, ...

  4. 洛谷 P1204 &lbrack;USACO1&period;2&rsqb;挤牛奶Milking Cows Label:模拟Ex 74分待查

    题目描述 三个农民每天清晨5点起床,然后去牛棚给3头牛挤奶.第一个农民在300秒(从5点开始计时)给他的牛挤奶,一直到1000秒.第二个农民在700秒开始,在 1200秒结束.第三个农民在1500秒开 ...

  5. 洛谷 P1204 &lbrack;USACO1&period;2&rsqb;挤牛奶Milking Cows

    题目描述 三个农民每天清晨5点起床,然后去牛棚给3头牛挤奶.第一个农民在300秒(从5点开始计时)给他的牛挤奶,一直到1000秒.第二个农民在700秒开始,在 1200秒结束.第三个农民在1500秒开 ...

  6. &lbrack;USACO1&period;2&rsqb;挤牛奶Milking Cows

    题目描述 三个农民每天清晨5点起床,然后去牛棚给3头牛挤奶.第一个农民在300秒(从5点开始计时)给他的牛挤奶,一直到1000秒.第二个农民在700秒开始,在 1200秒结束.第三个农民在1500秒开 ...

  7. 【洛谷P1204】【USACO1&period;2】挤牛奶Milking Cows

    P1204 [USACO1.2]挤牛奶Milking Cows 题目描述 三个农民每天清晨5点起床,然后去牛棚给3头牛挤奶.第一个农民在300秒(从5点开始计时)给他的牛挤奶,一直到1000秒.第二个 ...

  8. USACO Training Section 1&period;2 挤牛奶Milking Cows

    题目描述 三个农民每天清晨5点起床,然后去牛棚给3头牛挤奶.第一个农民在300秒(从5点开始计时)给他的牛挤奶,一直到1000秒.第二个农民在700秒开始,在 1200秒结束.第三个农民在1500秒开 ...

  9. 题解 P1208 【&lbrack;USACO1&period;3&rsqb;混合牛奶 Mixing Milk】

    其实根本没有一楼dalao描述的那么麻烦...... 一楼dalao其实吧,采用了一种纯属模拟的方式. 下面是我的*思想 但是一个个地做减法是不是太慢了?(*思想) 于是我们是不是可以直接进行 ...

随机推荐

  1. Navicat for mysql 远程连接 mySql数据库10061、1045错误

    原文地址:http://www.111cn.net/database/mysql/46377.htm 有朋友可能会碰到使用Navicat for mysql 远程连接 mySql数据库会提示10061 ...

  2. IE的&commat;cc&lowbar;on条件编译

    1: alert("浏览器版本为:"+sSuffix) 用来判断浏览器的版本很好用 var b = /*@cc_on!@*/false; 其中/*@cc_on ..... @*/之 ...

  3. Struct 和 Union 的详细区别

    Union: 共用体 Struct:结构体 两者的区别: 1:共用体和结构体都是由多个不同的数据类型成员组成, 但在任何同一时刻, 共用体只存放一个被选中的成员, 而结构体则存放所有的成员变量. 2: ...

  4. linux 硬盘

    df -hT 查看格式 各种文件 mount命令 可以挂载那些块设备:光盘.磁盘分区.U盘 光盘:文件系统:iso9660 iso文件文件系统:iso9660 iso文件可以进行挂载的 mount c ...

  5. 【angularjs】使用angularjs模拟淘宝首页-淘宝头条滚动效果

    <!DOCTYPE html> <html> <head> <meta charset="UTF-8"> <title> ...

  6. centos6&period;5环境基于corosync&plus;cman&plus;rgmanager实现RHCS及iscsi&plus;gfs2&plus;clvm的文件系统集群

    centos6.5环境基于corosync+cman+rgmanager实现RHCS及iscsi+gfs2+clvm文件系统集群 一.环境准备 服务器列表: ansible server : 192. ...

  7. jQuery基础(1)

    一.jQuery的介绍 1.为什么要使用jQuery? 在用js写代码时,会遇到一些问题,如下: 1)window.onload 事件有事件覆盖的问题,因此只能写一个事件: 2)代码容错性差: 3)浏 ...

  8. Ajax与XMLHttpRequest随笔

    1.XMLHttpRequest对象 创建XHR对象:let xhr = new XMLHttpRequest(); open():启动一个请求准备发送 open()接收3个参数:请求类型('GET' ...

  9. &period;NET设计模式(4):建造者模式(Builder Pattern)(转载)

    概述 在 软件系统中,有时候面临着“一个复杂对象”的创建工作,其通常由各个部分的子对象用一定的算法构成:由于需求的变化,这个复杂对象的各个部分经常面临着剧 烈的变化,但是将它们组合在一起的算法确相对稳 ...

  10. Knight Moves(广搜BFS)

    Description A friend of you is doing research on the Traveling Knight Problem (TKP) where you are to ...