Submission #416815

#	Time	Username	Problem	Language	Result	Execution time	Memory
416815		FerThugGato12500	Teams (IOI15_teams)	C++17	0 / 100	466 ms	286420 KiB

teams

#include "teams.h"

#include <bits/stdc++.h>
using namespace std;
const int lmt  = 500005;
const int MOD = 1000000007;

#define f first 
#define S second
#define ll long long
#define ld long double
#define ull unsigned long long
#define forn(i, n) for(int i = 0; i < int(n); i++)
#define for1(i, n) for(int i = 1; i < int(n); i++)
#define forv(i,a,n) for(int i = int(a); i < int(n); i++)
#define rof(i, n) for(int i = int(n); i >= 0; i--)
#define rofv(i,a,n) for(int i = int(n); i >= int(a); i--)
#define pb push_back
#define ins insert
#define pai pair<int, int>
#define pal pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define vld vector<long double>
struct wer{
    int A, B;
};
bool operator < (const wer &a, const wer &b){
    return a.A < b.A;
}
int n;
wer p[lmt];
vi st[lmt*4];
int lessa[lmt*4];
struct ST{
    void build(){
        build(0,n-1,0);
        return;
    }
    void build(int ini, int fin, int ind){
        if(ini==fin){
            st[ind].pb(p[ini].B);
            return;
        }
        int mit = (ini+fin)/2, ls = (ind*2)+1, rs = (ind*2)+2;
        build(ini, mit, ls);
        build(mit+1, fin, rs);
        int a = 0, b = 0;
        while(a<st[ls].size() || b<st[rs].size()){
            if(b==st[rs].size() ||  st[ls][a]>=st[rs][b]){
                st[ind].pb(st[ls][a]);
                a++;
            }else{
                st[ind].pb(st[rs][b]);
                b++;
            }
        }
        return;
    }
    int x, v, l;
    bool query(int stf, int stf2){
        if(stf2==-1){
            lessa[0]=0;
            return false;
        }
        x = v = stf; l = stf2;
        query(0, n-1, 0);
        if(v>0){
            lessa[0] = -1;
            return false;
        }
        return true;
    }
    int find(int ind, int X){
        int ini = lessa[ind], fin = st[ind].size()-1;
        if(st[ind][ini]<x){
            return lessa[ind]-1;
        }
        while(ini+1<fin){
            int mit = (ini+fin)/2;
            if(st[ind][mit]>=X){
                ini = mit;
            }else{
                fin = mit-1;
            }
        }
        if(st[ind][fin]>=X){
            return fin;
        }
        return ini;
    }
    void upd(int ind){
        int ls = (ind*2)+1, rs = (ind*2)+2;
        if(lessa[ind]==0 || lessa[ls]>0 || lessa[rs]>0) {
            return;
        }
        int V = lessa[ind];
        if(lessa[ls]==-1){
            int LS = (2*ls)+1, RS = (2*ls)+2;
            if(ind*2<n*4){
                lessa[LS] = lessa[RS] = -1;
            }
            lessa[ls] = 0;
        }
        if(lessa[rs]==-1){
            int LS = (2*rs)+1, RS = (2*rs)+2;
            if(ind*2<n*4){
                lessa[LS] = lessa[RS] = -1;
            }
            lessa[rs] = 0;
        }
        int t = st[ind][lessa[ind]-1];
        int c = find(rs, t)+1;
        if(c<=V){
            lessa[rs] = c;
            lessa[ls] = V-c;
        }else{
            lessa[rs] = V;
        }
        return;
    }
    void query(int ini, int fin, int ind){
        int mit = (ini+fin)/2, ls = (ind*2)+1, rs = (ind*2)+2;
        if(ini>l||fin<0){
            return;
        }
        if(lessa[ind]==-1){
            lessa[ind] = 0;
            if(ini!=fin){
                lessa[rs] = lessa[ls] = -1;
            }
        }
        if(ini>=0 && fin<=l){
            if(v==0) return;
            int r = (find(ind, x) - lessa[ind])+1;
            if(r<=v){
                v-=r;
                lessa[ind] += r;
            }else{
                lessa[ind] += v;
                v=0;
            }
            return;
        }
        upd(ind); 
        query(mit+1, fin, rs);
        query(ini, mit, ls);
        return;
    }
};
int alierputoxd[lmt];
ST mqun;
void init(int N, int A[], int B[]){
    n=N;
    forn(i, n) p[i].A = A[i];
    forn(i, n) p[i].B = B[i];
    sort(p, p+n);
    forn(i, n-1){
        if(p[i].A != p[i+1].A){
            alierputoxd[p[i].A] = i;
        }
    }
    alierputoxd[p[n-1].A] = n-1;
    alierputoxd[0] = -1;
    for1(i,n+1){
        if(!alierputoxd[i] && !(i == 1 && p[0].A==1)){
            alierputoxd[i] = alierputoxd[i-1];
        }
    }
    mqun.build();
    return;
}
int can(int M, int K[]){
    sort(K, K+M);
    reverse(K, K+M);
	forn(i, M){
		int x = K[i];
        if(!mqun.query(x, alierputoxd[x])){
            return false;
        }
    }
    return true;
}

Compilation message (stderr)

teams.cpp: In member function 'void ST::build(int, int, int)':
teams.cpp:49:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         while(a<st[ls].size() || b<st[rs].size()){
      |               ~^~~~~~~~~~~~~~
teams.cpp:49:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |         while(a<st[ls].size() || b<st[rs].size()){
      |                                  ~^~~~~~~~~~~~~~
teams.cpp:50:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |             if(b==st[rs].size() ||  st[ls][a]>=st[rs][b]){
      |                ~^~~~~~~~~~~~~~~
teams.cpp: In member function 'int ST::find(int, int)':
teams.cpp:75:51: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   75 |         int ini = lessa[ind], fin = st[ind].size()-1;
      |                                     ~~~~~~~~~~~~~~^~

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