Submission #668922

#	Time	Username	Problem	Language	Result	Execution time	Memory
668922		victor_gao	Teams (IOI15_teams)	C++17	21 / 100	4066 ms	285504 KiB

teams

#include <bits/stdc++.h>
#define pii pair<int,int>
#define x first
#define y second
#define MAXN 110005
#define BK 350
using namespace std;
struct BIT{
    int cnt=0,n,low,no,arr[MAXN+3];
    void init(int _n){
        n=_n; cnt=0; no=0; low=0;
        for (int i=0;i<=n;i++)
            arr[i]=0;
    }
    void modify(int p,int c){
        for (;p<=n;p+=(p&-p))
            arr[p]+=c;
    }
    int Query(int p){
        int ans=0;
        for (;p>0;p-=(p&-p))
            ans+=arr[p];
        return ans;
    }
    void change_low(int nxt){ low=nxt; no=query(low-1); }
    void out(int p,int c){ cnt-=c; modify(p,-c); }
    void in(int p,int c){ modify(p,c); cnt+=c; }
    int query(int r){ return Query(max(r,low-1))-no; }
}all[BK];
int l[MAXN],r[MAXN],n;
vector<pii>arr,change_arr;
vector<pair<int,pii> >change;
vector<int>onlyl;
void init(int N, int A[], int B[]) {
    n=N; arr.clear();
    for (int i=0;i<300;i++)
        all[i].init(n);
    for (int i=0;i<n;i++){
        l[i]=A[i];
        r[i]=min(B[i],n);
        arr.push_back({l[i],r[i]});
    }
    sort(arr.begin(),arr.end());
    for (int i=0;i<n;i++){
        all[i/BK].in(arr[i].y,1);
        onlyl.push_back(arr[i].x);
    }
}
int count(int now,int r,int qus){
    int i,ans=0;
    for (i=0;i*BK+BK-1<=r;i++){
        int p=all[i].query(now);
        ans=(ans+p);
    }
    i=i*BK;
    for (;i<=r;i++){
        if (arr[i].y<=now&&arr[i].y>=qus){
            ans++;
        }
    }
    return ans;
}
void make_change(int val,int r,int need_out){
    int i=0,qus=need_out;
 //   assert(count(val,r,need_out)>=need_out);
    for (i=0;i*BK+BK-1<=r;i++){
        int left=all[i].query(val-1);
        all[i].change_low(max(val,all[i].low));
        need_out-=left;
    }
    if (need_out==0) return;
    i=i*BK;
    for (;i<=r&&need_out;i++){
        if (arr[i].y<val&&arr[i].y>=max(qus,all[i/BK].low)){
            change_arr.push_back({i,arr[i].y});
            all[i/BK].out(arr[i].y,1);
            change.push_back({i/BK,{arr[i].y,1}});
            need_out--; arr[i].y=0;
        }
    }
    i=0;
    for (;i*BK+BK-1<=r&&need_out;i++){
        int left=all[i].query(val);
        if (!left) continue;
        if (left>=need_out)
            break;
        else {
            need_out-=left;
            all[i].change_low(max(val+1,all[i].low));
        }
    }
    i=i*BK;
    for (;i<=r&&need_out;i++){
        if (arr[i].y==val&&arr[i].y>=max(all[i/BK].low,qus)){
            change_arr.push_back({i,arr[i].y});
            all[i/BK].out(arr[i].y,1);
            change.push_back({i/BK,{arr[i].y,1}});
            need_out--; arr[i].y=0;
        }
    }
  //  assert(need_out==0);
}
void reset_before_query(){
    for (auto i:change)
        all[i.x].in(i.y.x,i.y.y);
    change.clear();
    for (auto i:change_arr)
        arr[i.x].y=i.y;
    change_arr.clear();
    for (int i=0;i<300;i++)
        all[i].change_low(0);
}
void reset(int val){
    for (int i=0;i<300;i++)
        all[i].change_low(max(val,all[i].low));
}
int can(int M, int K[]) {
    sort(K,K+M);
    reset_before_query();
    for (int i=0;i<M;i++){
        reset(K[i]);
        int canr=upper_bound(onlyl.begin(),onlyl.end(),K[i])-onlyl.begin()-1;
        int l=min(K[i],n+1),r=n+1;
        while (l<r){
            int mid=(l+r)>>1;
            int have=count(mid,canr,K[i]);
            if (have>=K[i]) r=mid;
            else l=mid+1;
        }
        if (l==n+1) return 0;
        else make_change(l,canr,K[i]);
    }
    return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int count(int, int, int)':
teams.cpp:49:23: warning: declaration of 'r' shadows a global declaration [-Wshadow]
   49 | int count(int now,int r,int qus){
      |                   ~~~~^
teams.cpp:30:13: note: shadowed declaration is here
   30 | int l[MAXN],r[MAXN],n;
      |             ^
teams.cpp: In function 'void make_change(int, int, int)':
teams.cpp:63:30: warning: declaration of 'r' shadows a global declaration [-Wshadow]
   63 | void make_change(int val,int r,int need_out){
      |                          ~~~~^
teams.cpp:30:13: note: shadowed declaration is here
   30 | int l[MAXN],r[MAXN],n;
      |             ^
teams.cpp: In function 'int can(int, int*)':
teams.cpp:122:75: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
  122 |         int canr=upper_bound(onlyl.begin(),onlyl.end(),K[i])-onlyl.begin()-1;
      |                  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
teams.cpp:123:13: warning: declaration of 'l' shadows a global declaration [-Wshadow]
  123 |         int l=min(K[i],n+1),r=n+1;
      |             ^
teams.cpp:30:5: note: shadowed declaration is here
   30 | int l[MAXN],r[MAXN],n;
      |     ^
teams.cpp:123:29: warning: declaration of 'r' shadows a global declaration [-Wshadow]
  123 |         int l=min(K[i],n+1),r=n+1;
      |                             ^
teams.cpp:30:13: note: shadowed declaration is here
   30 | int l[MAXN],r[MAXN],n;
      |             ^

• Subtask 1: 21 / 21
• Subtask 2: 0 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23