Submission #668550

#	Time	Username	Problem	Language	Result	Execution time	Memory
668550		victor_gao	Teams (IOI15_teams)	C++17	0 / 100	4088 ms	246476 KiB

teams

#include <bits/stdc++.h>
#include "teams.h"
#define pii pair<int,int>
#define x first
#define y second
#define MAXN 100005
#define BK 350
using namespace std;
struct BIT{
    int cnt=0,n,low,no,arr[MAXN];
    void init(int _n){
        n=_n; cnt=0; no=0;
        for (int i=0;i<=n+1;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,1); cnt+=c; }
    int query(int r){ return Query(r)-no; }
}all[300];
int l[MAXN],r[MAXN],n;
vector<pii>arr,change_arr;
vector<pair<int,pii> >change;
vector<int>val[300],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=1;i<=n;i++){
        l[i]=A[i-1];
        r[i]=B[i-1];
        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);
        val[i/BK].push_back(arr[i].y);
        onlyl.push_back(arr[i].x);
    }
    for (int i=0;i<300;i++)
        sort(val[i].begin(),val[i].end());
}
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;
   // cout<<"count block "<<ans<<" "<<i<<'\n';
    for (;i<=r;i++){
        if (arr[i].y<=now&&arr[i].y>=qus){
   //         cout<<"check "<<i<<" "<<arr[i].y<<" in "<<qus<<" "<<now<<'\n';
            ans++;
        }
    }
    return ans;
}
void make_change(int val,int r,int need_out){
    int i=0,qus=need_out;
    for (i=0;i*BK+BK-1<=r;i++){
        int left=all[i].query(val);
        all[i].change_low(min(need_out,left));
        need_out-=min(need_out,left);
    }
    
    i=i*BK;
    for (;i<=r&&need_out;i++){
      //  cout<<"try "<<i<<" "<<arr[i].y<<" in "<<qus<<" "<<val<<'\n';
        if (arr[i].y<=val&&arr[i].y>=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;
        }
    }
}
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].no));
}
int can(int M, int K[]) {
    sort(K,K+M);
    reset_before_query();
    /*
    cout<<"start :\n";
    for (int j=0;j*BK<=n;j++){
        for (int k=1;k<=5;k++)
            cout<<all[j].query(k)-all[j].query(k-1)<<' ';
        cout<<'\n';
    }
    */
    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=K[i],r=n+1;
        while (l<r){
            int mid=(l+r)>>1;
            int have=count(mid,canr,K[i]);
          //  cout<<i<<" : "<<mid<<" "<<have<<' '<<canr<<'\n';
            if (have>=K[i]) r=mid;
            else l=mid+1;
        }
      //  cout<<K[i]<<" -> "<<l<<'\n';
        if (l==n+1) return 0;
        else make_change(l,canr,K[i]);
        /*
        cout<<"after \n";
        for (int j=0;j*BK<=n;j++){
            for (int k=1;k<=5;k++)
                cout<<all[j].query(k)-all[j].query(k-1)<<' ';
            cout<<'\n';
        }
        */
    }
    return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int count(int, int, int)':
teams.cpp:53:23: warning: declaration of 'r' shadows a global declaration [-Wshadow]
   53 | int count(int now,int r,int qus){
      |                   ~~~~^
teams.cpp:31:13: note: shadowed declaration is here
   31 | int l[MAXN],r[MAXN],n;
      |             ^
teams.cpp: In function 'void make_change(int, int, int)':
teams.cpp:69:30: warning: declaration of 'r' shadows a global declaration [-Wshadow]
   69 | void make_change(int val,int r,int need_out){
      |                          ~~~~^
teams.cpp:31:13: note: shadowed declaration is here
   31 | int l[MAXN],r[MAXN],n;
      |             ^
teams.cpp:69:22: warning: declaration of 'val' shadows a global declaration [-Wshadow]
   69 | void make_change(int val,int r,int need_out){
      |                  ~~~~^~~
teams.cpp:34:12: note: shadowed declaration is here
   34 | vector<int>val[300],onlyl;
      |            ^~~
teams.cpp: In function 'void reset(int)':
teams.cpp:98:16: warning: declaration of 'val' shadows a global declaration [-Wshadow]
   98 | void reset(int val){
      |            ~~~~^~~
teams.cpp:34:12: note: shadowed declaration is here
   34 | vector<int>val[300],onlyl;
      |            ^~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:115:75: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
  115 |         int canr=upper_bound(onlyl.begin(),onlyl.end(),K[i])-onlyl.begin()-1;
      |                  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
teams.cpp:116:13: warning: declaration of 'l' shadows a global declaration [-Wshadow]
  116 |         int l=K[i],r=n+1;
      |             ^
teams.cpp:31:5: note: shadowed declaration is here
   31 | int l[MAXN],r[MAXN],n;
      |     ^
teams.cpp:116:20: warning: declaration of 'r' shadows a global declaration [-Wshadow]
  116 |         int l=K[i],r=n+1;
      |                    ^
teams.cpp:31:13: note: shadowed declaration is here
   31 | int l[MAXN],r[MAXN],n;
      |             ^

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