# Codeforces Round 546 (Div. 2)

2019/03/13 01:48

<a href="https://codeforces.com/contest/1136" target="_blank" style="font-size:24px;"><strong>传送门</strong></a>

### A - Nastya Is Reading a Book (签到)

#### 题意

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=2e5+50;
const ll inf=1e17;
typedef unsigned long long ull;
int l[maxn],r[maxn];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d%d",&l[i],&r[i]);
int k;
scanf("%d",&k);
int num=n+1;
for(int i=1;i<=n;i++){
if(k>r[i])continue;
else{
num=i;
break;
}
}
cout<<n-num+1<<endl;
return 0;
}


### B - Nastya Is Playing Computer Games (模拟)

#### 题意

1：向左走或者向右走，

2：把一个石头扔到其他任意一个井盖上面

3：取走金币

#### 思路

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=2e5+50;
const ll inf=1e17;
typedef unsigned long long ull;

int main()
{
int n,k;
scanf("%d%d",&n,&k);
if(n==1||n==k)printf("%d\n",n*3);
else{
int sum=3*n;
sum+=min((k-1),(n-k));
printf("%d\n",sum);
}
return 0;
}


### C - Nastya Is Transposing Matrices (神奇)

#### 思路

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=2e5+50;
const ll inf=1e17;
typedef unsigned long long ull;
vector<int>v1[500*500+5];
vector<int>v2[500*500+5];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int a;
scanf("%d",&a);
v1[i+j].push_back(a);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int a;
scanf("%d",&a);
v2[i+j].push_back(a);
}
}

for(int i=1;i<=n+m;i++){
sort(v1[i].begin(),v1[i].end());
sort(v2[i].begin(),v2[i].end());
if(v1[i]!=v2[i])puts("NO"),exit(0);
}
puts("YES");
return 0;
}


### D - Nastya Is Buying Lunch (贪心)

#### 思路

1：可以让n和她交换位置

2：不可以让n和她交换位置

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=6e5+50;
const ll inf=1e17;
typedef unsigned long long ull;

int a[maxn];
map<int,int>mp[maxn];
int vis[maxn];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
for(int i=1;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
mp[u][v]=1;
if(v==a[n])vis[u]=1;
}
for(int i=n-1;i>=1;i--){
if(vis[a[i]]){
for(int j=i+1;j<n;j++){
if(mp[a[j-1]].find(a[j])!=mp[a[j-1]].end()){
swap(a[j],a[j-1]);
}
else break;
}
}
}
int ans=0;
for(int i=n-1;i>=1;i--){
if(vis[a[i]])ans++;
else break;
}
printf("%d\n",ans);
return 0;
}


### E - Nastya Hasn't Written a Legend （线段树）

#### 题意

1：区间求$\sum_{i=l}^{r}a_i$

2：给单点$a_i$加$x$ 同时会有连锁反应，若$a_p+k_p>a_{p+1}$,则$a_{p+1}$ 更新为$a_p+k_p$ ，同理更新到$a_p+2$ 知道不能更新

#### 思路

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=2e5+50;
const ll inf=1e17;
typedef unsigned long long ull;

int n,m;
ll a[maxn],k[maxn],ks[maxn];
struct SegTree{
ll sum[maxn<<2],flag[maxn<<2];
void build(int o,int l,int r){
flag[o]=inf;
if(l==r){
sum[o]=a[l]-k[l-1];return;
}
int mid=(l+r)/2;
build(o<<1,l,mid);
build(o<<1|1,mid+1,r);
sum[o]=sum[o<<1]+sum[o<<1|1];
}
void push_down(int o,int l,int r){
if(flag[o]==inf)return;
int mid=(l+r)/2;
flag[o<<1]=flag[o<<1|1]=flag[o];
sum[o<<1]=flag[o]*(mid-l+1);
sum[o<<1|1]=flag[o]*(r-mid);
flag[o]=inf;
}
void update(int o,int l,int r,int ql,int qr,ll v){
if(ql<=l&&r<=qr){
flag[o]=v;
sum[o]=v*(r-l+1);
return;
}
int mid=(l+r)/2;
push_down(o,l,r);
if(ql<=mid)update(o<<1,l,mid,ql,qr,v);
if(qr>mid)update(o<<1|1,mid+1,r,ql,qr,v);
sum[o]=sum[o<<1]+sum[o<<1|1];
}
ll query(int o,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr)return sum[o];
int mid=(l+r)/2;
push_down(o,l,r);
ll res=0;
if(ql<=mid)res+=query(o<<1,l,mid,ql,qr);
if(qr>mid)res+=query(o<<1|1,mid+1,r,ql,qr);
return res;
}
}segtree;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
for(int i=1;i<n;i++)scanf("%lld",&k[i]);
for(int i=2;i<n;i++)k[i]+=k[i-1];
for(int i=1;i<n;i++)ks[i]=ks[i-1]+k[i];
segtree.build(1,1,n);
scanf("%d",&m);
while(m--){
char op[5];int l,r;
scanf("%s%d%d",op,&l,&r);
if(op[0]=='s')printf("%lld\n",segtree.query(1,1,n,l,r)+ks[r-1]-(l>=2?ks[l-2]:0));
else{
int L=l,R=n,mid,ans=l;
ll sum=segtree.query(1,1,n,l,l)+r;
// cout<<"sum="<<sum<<endl;
while(L<=R){
mid=(L+R)/2;
// cout<<"mid="<<mid<<endl;
if(sum>segtree.query(1,1,n,mid,mid)){
ans=mid;
L=mid+1;
}
else
R=mid-1;
}
// cout<<"ans="<<ans<<endl;
segtree.update(1,1,n,l,ans,sum);
}
}
return 0;
}


0
0 收藏

0 评论
0 收藏
0