Educational Codeforces Round 76

https://codeforces.com/contest/1257

A - Two Rival Students

AC:+0:11(+)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int n,x,ta,tb;
        scanf("%d%d%d%d",&n,&x,&ta,&tb);
        int a = min(ta,tb);
        int b = max(ta,tb);
        int l = a-1;
        int r = n-b;
        int cur = b-a;
//        cout<<x<<a<<b<<endl;
        if(x>=(l+r)){
            printf("%d",(l+r)+cur);
        }
        else{
            printf("%d",x+cur);
        }
        if(t!=0)
            printf("\n");
    }
    return 0;
}

B - Magic Stick

AC:+0:49(+)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long LL;
LL a[100],b[100];
const LL INF = 0x3f3f3f3f;
int cnt;
void func(){
    a[1] = 2;
    b[1] = 3;
    for(int i = 2;;++i){
        cnt = i;
        if(a[i-1]>INF)
            break;
        a[i] = a[i-1]*2;
        b[i] = b[i-1]*3;
        if(b[i]>INF)
            b[i] = INF;
    }
}
bool flag;
LL font_x;
void solved(LL x,LL y){
    font_x = x;
    for(int i = cnt-1;i>=1;--i){
        if(x>=a[i]){
            LL tt = x/a[i];
            if(tt*b[i]<=font_x)
                continue;
            if(tt*b[i]>=y){
                cout<<"YES"<<endl;
                flag = true;
                return;
            }else{
                //cout<<tt*b[i]<<endl;
                solved(tt*b[i],y);
            }
        }
        if(flag) return;
    }
}
int main(){
    func();
    int t;
    scanf("%d",&t);
    while(t--){
        LL x,y;
        cin>>x>>y;
        if(x>=y){
            cout<<"YES"<<endl;
            continue;
        }
        flag = false;
        solved(x,y);
        if(!flag)
            cout<<"NO"<<endl;
    }
    return 0;
}

C - Dominated Subarray

AC:1:12(+)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
using namespace std;
typedef long long LL;
const LL INF = 0x3f3f3f3f;
map<int,int>mm;
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        mm.clear();
        int n,x,ans = -1;
        scanf("%d",&n);
        for(int i = 1;i<=n;++i){
            scanf("%d",&x);
            if(mm.count(x)==0){
                mm[x] = i;
            }else{
                if(ans==-1) ans = (i-mm[x]+1);
                else        ans = min(ans,i-mm[x]+1);
                mm[x] = i;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

D - Yet Another Monster Killing Problem

AC:*(+1)

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
const int MAXN = 200010;
 
using namespace std;
struct node{
    int p,s;
}a[MAXN];
map<int,pair<int,int> >mm;
int num[MAXN],mon[MAXN];
bool cmp(const struct node&s1,const struct node&s2){
    if(s1.p==s2.p) return s1.s>s2.s;
    return s1.p<s2.p;
}
int find_binary(int n,int x){
    int l = 0,r = n-1;
    while(l<=r){
        int mid = (l+r)/2;
        if(a[mid].p==x)     return mid;
        else if(a[mid].p<x) l = mid+1;
        else                r = mid-1;
    }
    return l;
}
int main()
{
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--){
        mm.clear();
        int n,m,cnt = 0;
        cin>>n;
        for(int i = 0;i<n;++i)
            cin>>mon[i];
        cin>>m;
        for(int i = 0;i<m;++i){
            node tt;
            cin>>tt.p>>tt.s;
            if(mm.count(tt.p)==0){
                mm[tt.p] = make_pair(tt.s,cnt);
                a[cnt++] = tt;
            }else{
                if(tt.s>mm[tt.p].first){
                    mm[tt.p].first = tt.s;
                    a[mm[tt.p].second] = tt;
                }
            }
        }
        sort(a,a+cnt,cmp);
        num[cnt-1] = a[cnt-1].s;
        for(int i = cnt-2;i>=0;--i)
            num[i] = max(a[i].s,num[i+1]);
        bool flag = true;
        int ans = 0;
        for(int i = 0;i<n;){
            int tt = 0,font_s = 0x3f3f3f3f;
            while((i+tt)<n){
                int p = find_binary(cnt,mon[i+tt]);
                font_s = min(font_s,num[p]);
                if(p>=cnt || (tt+1)>font_s )
                    break;
                ++tt;
            }
            if(tt==0){
                flag = false;
                break;
            }
            i+=tt;
            ++ans;
        }
        if(flag)    cout<<ans<<endl;
        else        cout<<"-1"<<endl;
    }
    return 0;
}