Codeforces Round 914 (Div. 2)

A. Forked!

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;

void solve(){
    int a,b;
    int x,y;
    cin>>a>>b>>x>>y;
    map<pair<int,int>,int> board;
    vector<pair<int,int>> path;
    path.push_back({a,b});
    path.push_back({-a,b});
    path.push_back({a,-b});
    path.push_back({-a,-b});
    path.push_back({b,a});
    path.push_back({-b,a});
    path.push_back({b,-a});
    path.push_back({-b,-a});
    for(auto [u,v]:path) board[{x+u,y+v}]=1;
    int ans=0;
    cin>>x>>y;
    for(auto [u,v]:path){
        ans += (board[{x+u,y+v}]>0);
        board[{x+u,y+v}]--;
    }
    cout<<ans<<endl;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
    while(T--) solve();
    return 0;
}

B. Collecting Game

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;

const int N = 1e5 + 10;
int pre[N];
int ans[N];

void solve(){
    int n;
    cin>>n;
    vector<pair<int,int>> a;
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        a.push_back({x,i+1});
    }
    sort(a.begin(),a.end());
    pre[0]=a[0].first;
    for(int i=1;i<n;i++) pre[i] = pre[i-1] + a[i].first;
    vector<int> idx;
    idx.push_back(-1);
    for(int i=1;i<n;i++)
        if(a[i].first>pre[i-1])idx.push_back(i-1);
    if(idx.back()!=n-1)idx.push_back(n-1);
    for(int i=1;i<idx.size();i++)
    {
        int l=idx[i-1];
        int r=idx[i];
        int len = r;
        //cout<<l<<" "<<r<<endl;
        for(int j=l+1;j<=r;j++)
        {
            ans[a[j].second] = len;
            //cout<<ans[a[j].second]<<" "<<len<<endl;
        }
    }
    for(int i=1;i<=n;i++)
        cout<<ans[i]<<" ";
    cout<<endl;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
    while(T--) solve();
    return 0;
}

C. Array Game

暴力

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;

const int N = 2e3 + 10;
int a[N];
int n,k;

void solve(){
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+1+n);
    if(k>=3){
        cout<<0<<endl;
        return;
    }
    if(k==1){
        priority_queue<int,vector<int>,greater<int>> path;
        for(int i=1;i<=n;i++)
            for(int j=i+1;j<=n;j++)
                path.push(abs(a[i]-a[j]));
        cout<< min(path.top() , a[1]) <<endl;
        return;
    }
    vector<int> b;
    for(int i=1;i<=n;i++)
           for(int j=i+1;j<=n;j++)
            b.push_back(abs(a[i]-a[j]));
    sort(b.begin(),b.end());
    priority_queue<int,vector<int>,greater<int>> path;
    for(int i=1;i<=n;i++){
        int idx=lower_bound(b.begin(),b.end(),a[i])-b.begin();
        if(idx<b.size())path.push(abs(a[i]-b[idx]));
        if(idx>0) path.push(abs(a[i]-b[idx-1]));
    }
    cout<<min({a[1],b[0],path.top()})<<endl;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
    while(T--) solve();
    return 0;
}

D2. Set To Max

好像又是个线段树啊。等考完试有时间我一定好好补。

ST表感觉不太实用，不太想写。

算了我还是搓个线段树吧，好久没写过了感觉都生疏了。

还是挺简单的，不涉及区间修改的话

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;

const int N = 2e5 + 10;
struct Node{
    int l,r;
    int val;
}maTree[N*3],miTree[N*3];

void build(int i,int l,int r){
    maTree[i].l = l;
    maTree[i].r = r;
    maTree[i].val = 0;

    miTree[i].l = l;
    miTree[i].r = r;
    miTree[i].val = 0;

    if(l==r) return;
    int mid = l + r >> 1;
    build(i<<1,l,mid);
    build((i<<1)|1,mid+1,r);
}

void update1(int i,int k,int val){
    if(maTree[i].l==k&&maTree[i].r==k){
        maTree[i].val = val;
        return;
    }
    int mid = (maTree[i].l + maTree[i].r) >> 1;
    if(k<=mid) update1(i<<1,k,val);
    else       update1((i<<1)|1,k,val);
    maTree[i].val = max(maTree[i<<1].val , maTree[(i<<1)|1].val);
}

int query1(int i,int l,int r){
    if(maTree[i].l == l && maTree[i].r == r) return maTree[i].val;
    int mid = (maTree[i].l + maTree[i].r) >> 1;
    if(r<=mid) return query1(i<<1,l,r);
    else if(l > mid) return query1((i<<1)|1,l,r);
    else return max(query1(i<<1,l,mid),query1((i<<1)|1,mid + 1,r));
}

void update2(int i,int k,int val){
    if(miTree[i].l==k&&miTree[i].r==k){
        miTree[i].val = val;
        return;
    }
    int mid = (miTree[i].l + miTree[i].r) >> 1;
    if(k<=mid) update2(i<<1,k,val);
    else       update2((i<<1)|1,k,val);
    miTree[i].val = min(miTree[i<<1].val , miTree[(i<<1)|1].val);
}

int query2(int i,int l,int r){
    if(miTree[i].l == l && miTree[i].r == r) return miTree[i].val;
    int mid = (miTree[i].l + miTree[i].r) >> 1;
    if(r<=mid) return query2(i<<1,l,r);
    else if(l > mid) return query2((i<<1)|1,l,r);
    else return min(query2(i<<1,l,mid),query2((i<<1)|1,mid + 1,r));
}

int a[N],b[N];
int n;

void solve(){
    cin>>n;
    build(1,1,n);
    vector<vector<int>> path(n+1);
    for(int i=1;i<=n;i++) path[i].push_back(0);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        path[a[i]].push_back(i);
        update1(1,i,a[i]);
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
        update2(1,i,b[i]);
        path[i].push_back(n+1);
    }
    for(int i=1;i<=n;i++)
        if(a[i]>b[i])
        {
            cout<<"NO"<<endl;
            return;
        }
    for(int i=1;i<=n;i++){
        if(a[i]!=b[i]){
            int idx=lower_bound(path[b[i]].begin(),path[b[i]].end(),i)-path[b[i]].begin();
            int r=path[b[i]][idx];
            int l=path[b[i]][idx-1];
            bool ok=false;
            if(r!=n+1&&query1(1,i,r) <= b[i] && query2(1,i,r)>=b[i])   ok=true;
            if(!ok&&l!=0&& query1(1,l,i) <= b[i] && query2(1,l,i)>=b[i]) ok=true;
            if(!ok){
                cout<<"NO"<<endl;
                return;
            }
        }
    }
    cout<<"YES"<<endl;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
    while(T--) solve();
    return 0;
}