Submission #668554

#	Time	Username	Problem	Language	Result	Execution time	Memory
668554		victor_gao	Teams (IOI15_teams)	C++17	0 / 100	4075 ms	246424 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; low=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,c); 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;
    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;
    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++){
        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();
    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]);
            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: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:67:30: warning: declaration of 'r' shadows a global declaration [-Wshadow]
   67 | 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:67:22: warning: declaration of 'val' shadows a global declaration [-Wshadow]
   67 | 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:95:16: warning: declaration of 'val' shadows a global declaration [-Wshadow]
   95 | 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:104:75: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
  104 |         int canr=upper_bound(onlyl.begin(),onlyl.end(),K[i])-onlyl.begin()-1;
      |                  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
teams.cpp:105:13: warning: declaration of 'l' shadows a global declaration [-Wshadow]
  105 |         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:105:20: warning: declaration of 'r' shadows a global declaration [-Wshadow]
  105 |         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