Conan_2009

71

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
double n;
double lf(double x){return x*x*x;}
int main(){
cin>>n;
double l=-10000,r=10000;
while(r-l>=1e-7){
double mid=(l+r)/2;
if(lf(mid)>=n) r=mid;
else l=mid;
}
cout<<fixed<<setprecision(6)<<l;
return 0;
}


#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
int n,q,a[1000000];
int main(){
scanf("%d%d",&n,&q);
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
while(q--){
int k;
scanf("%d",&k);
int l=0,r=n-1,mid=0;
while(l<r){
mid=(l+r)/2;
if(a[mid]<k) l=mid+1;
else r=mid;
}
if(a[l]!=k){
printf("-1 -1\n");
continue;
}
int l1=1,r1=n;
while(l1+1<r1){
mid=(l1+r1)/2;
if(a[mid]<=k) l1=mid;
else r1=mid;
}
cout<<l<<' '<<l1<<'\n';
}
return 0;
}


#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
long long n,a[1000000],tmp[1000000],res;
void merge_sort(long long q[], int l, int r)
{
if (l >= r) return;

int mid = l + r >> 1;
merge_sort(q, l, mid);
merge_sort(q, mid + 1, r);

int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r)
if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
else res+=mid-i+1,tmp[k ++ ] = q[j ++ ];

while (i <= mid) tmp[k ++ ] = q[i ++ ];
while (j <= r) tmp[k ++ ] = q[j ++ ];

for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}
int main(){
scanf("%lld",&n);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
merge_sort(a,1,n);
cout<<res;
return 0;
}


#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
int n,a[1000000],tmp[1000000];
void merge_sort(int q[], int l, int r)
{
if (l >= r) return;

int mid = l + r >> 1;
merge_sort(q, l, mid);
merge_sort(q, mid + 1, r);

int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r)
if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
else tmp[k ++ ] = q[j ++ ];

while (i <= mid) tmp[k ++ ] = q[i ++ ];
while (j <= r) tmp[k ++ ] = q[j ++ ];

for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
merge_sort(a,1,n);
for(int i=1;i<=n;i++)
cout<<a[i]<<" ";
return 0;
}


#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
int n,a[1000000],k;
void quick_sort(int q[], int l, int r)
{
if (l >= r) return;
int i = l - 1, j = r + 1, x = q[(l+r)/2];
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}
quick_sort(q, l, j), quick_sort(q, j + 1, r);
}
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
quick_sort(a,1,n);
cout<<a[k];
return 0;
}


#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
int n,a[1000000];
void quick_sort(int q[], int l, int r)
{
if (l >= r) return;

int i = l - 1, j = r + 1, x = q[l + r >> 1];
while (i < j)
{
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j) swap(q[i], q[j]);
}
quick_sort(q, l, j), quick_sort(q, j + 1, r);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
quick_sort(a,1,n);
for(int i=1;i<=n;i++)
cout<<a[i]<<' ';
return 0;
}


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef pair<int,int> Pair; // 值与下标
const int N=100010;
int n,m,query;
int h[N],e[N<<1],ne[N<<1],idx; // 邻接表
int dist[N][2]; // 长度
Pair q[N*2]; // 队列
void add(int a,int b){ // 邻接表加边
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void bfs(){ // 预处理（BFS）
memset(dist,0x3f,sizeof(dist)); // 初距离始化为正无穷
int hh=0,tt=0;
q[0]={1,0},dist[1][0]=0; // 初始化队列起点
while(hh<=tt){ // 遍历
Pair t=q[hh++];
int ver=t.first,type=t.second; // ver与type为当前点编号
for(int i=h[ver];~i;i=ne[i]){ // 遍历邻接表表邻边
int j=e[i]; // 取出邻边编号
if(dist[j][type^1]>dist[ver][type]+1){ // 如果走一步的长度大于dist[j][type]+1
/*注：由于走一步就会变一下奇偶性，所以要用type^1*/
dist[j][type^1]=dist[ver][type]+1;
q[++tt]={j,type^1};
/* 刷新并将点更新到队列中 */
}
}
}
}
int main(){
cin.tie(0);
memset(h,-1,sizeof(h)); // 邻接表初始化
cin>>n>>m>>query;
for(int i=1;i<=m;i++){
int a,b;
cin>>a>>b;
}
bfs(); // 预处理（BFS）
while(query--){ // 循环处理工单
int a,l;
cin>>a>>l;
if(a==1&&h[1]==-1) puts("No"); // 特判
else if(dist[a][l&1]<=l) puts("Yes"); // 如果存在与L同奇偶性且比L小的路径，表示需要提供原材料
else puts("No"); // 如果不存在，表示不需要生产原材料
}
return 0;
}
/*
注：本程序使用拆点法，将一个点拆成一个偶点和
一个奇点，然后预处理偶点到偶点的最短距离与偶点
到奇点的最短距离，最后再进行判断
*/

/*

dist[v][0] : 1 ~ v 偶数路径最短路
dist[v][1] : 1 ~ v 奇数路径最短路
a,L
L是奇数，L>=dist[a][0]
L是偶数  L>=dist[a][1]
*/


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef pair<int,int> Pair; // 值与下标
const int N=100010;
int n,m,query;
int h[N],e[N<<1],ne[N<<1],idx; // 邻接表
int dist[N][2]; // 长度
Pair q[N*2]; // 队列
void add(int a,int b){ // 邻接表加边
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void bfs(){ // 预处理（BFS）
memset(dist,0x3f,sizeof(dist)); // 初距离始化为正无穷
int hh=0,tt=0;
q[0]={1,0},dist[1][0]=0; // 初始化队列起点
while(hh<=tt){ // 遍历
Pair t=q[hh++];
int ver=t.first,type=t.second; // ver与type为当前点编号
for(int i=h[ver];~i;i=ne[i]){ // 遍历邻接表表邻边
int j=e[i]; // 取出邻边编号
if(dist[j][type^1]>dist[ver][type]+1){ // 如果走一步的长度大于dist[j][type]+1
/*注：由于走一步就会变一下奇偶性，所以要用type^1*/
dist[j][type^1]=dist[ver][type]+1;
q[++tt]={j,type^1};
/* 刷新并将点更新到队列中 */
}
}
}
}
int main(){
cin.tie(0);
memset(h,-1,sizeof(h)); // 邻接表初始化
cin>>n>>m>>query;
for(int i=1;i<=m;i++){
int a,b;
cin>>a>>b;
}
bfs(); // 预处理（BFS）
while(query--){ // 循环处理工单
int a,l;
cin>>a>>l;
if(a==1&&h[1]==-1) puts("No"); // 特判
else if(dist[a][l&1]<=l) puts("Yes"); // 如果存在与L同奇偶性且比L小的路径，表示需要提供原材料
else puts("No"); // 如果不存在，表示不需要生产原材料
}
return 0;
}
/*
注：本程序使用拆点法，将一个点拆成一个偶点和
一个奇点，然后预处理偶点到偶点的最短距离与偶点
到奇点的最短距离，最后再进行判断
*/

/*

dist[v][0] : 1 ~ v 偶数路径最短路
dist[v][1] : 1 ~ v 奇数路径最短路
a,L
L是奇数，L>=dist[a][0]
L是偶数  L>=dist[a][1]
*/


#include <iostream>
#include <cstring>
using namespace std;
int t,n,m;
int p[1000][1000],tmp[100000];
int main(){
cin.tie(0);
scanf("%d%d%d",&t,&n,&m);
for(int i=1;i<=t;i++)
for(int j=1;j<=n;j++)
cin>>p[i][j];
for(int i=1;i<t;i++){
memset(tmp,0,sizeof(tmp));
for(int j=1;j<=n;j++)
if(p[i+1][j]>p[i][j])
for(int k=p[i][j];k<=m;k++)
tmp[k]=max(tmp[k],tmp[k-p[i][j]]+p[i+1][j]-p[i][j]);
m+=tmp[m];
}
cout<<m;
return 0;
}


#include <iostream>
#include <cstdio>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
struct huangxutao{ int time,price,flag; }a[100000];
int n,ans;
inline void debug(int x){cout<<x<<'\n';}
int main(){
cin.tie(0);
cin>>n;
int l=1,r=0;
for(int i=1;i<=n;i++){
int chuxing,Time,Price;
cin>>chuxing>>Price>>Time;
if(!chuxing)
a[++r]={Time,Price,1},ans+=Price;
else{
while(l<r&&Time-a[l].time>45) l++;
bool pan=true;
for(int j=l;j<=r;j++)
if(a[j].price>=Price&&a[j].flag){
pan=false;
a[j].flag=0;
break;
}
if(pan)
ans+=Price;
}
//      debug(ans);
}
cout<<ans;
return 0;
}