Submission #1016524

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016524		Muhammet	Teams (IOI15_teams)	C++17	34 / 100	4074 ms	73516 KiB

teams

#include <bits/stdc++.h>
#include "teams.h"

using namespace std;

#define ff first
#define ss second

int n, an;

vector <int> st, lz, st1, lz1;

vector <pair<int,int>> a;

int upd(int nd, int l, int r, int x, int y, int vl){
    st[nd] += ((r-l+1) * lz[nd]);
    lz[nd*2] += lz[nd];
    lz[nd*2+1] += lz[nd];
    lz[nd] = 0;
    if(l > y or r < x) return st[nd];
    if(l >= x and r <= y){
        lz[nd] += vl;
        st[nd] += ((r-l+1) * lz[nd]);
        lz[nd*2] += lz[nd];
        lz[nd*2+1] += lz[nd];
        lz[nd] = 0;
        return st[nd];
    }
    int md = (l + r) / 2;
    return st[nd] = upd(nd*2,l,md,x,y,vl) + upd(nd*2+1,md+1,r,x,y,vl);
} 

int fnd(int nd, int l, int r, int ind){
    st[nd] += ((r-l+1) * lz[nd]);
    lz[nd*2] += lz[nd];
    lz[nd*2+1] += lz[nd];
    lz[nd] = 0;
    if((r < ind) or (l > ind)) return st[nd];
    if(l == r){
        an = st[nd];
        return st[nd];
    }
    int md = (l + r) / 2;
    return st[nd] = fnd(nd*2,l,md,ind) + fnd(nd*2+1,md+1,r,ind);
}

void init(int N, int A[], int B[]) {
    n = N;
    a.resize(n);
    st.resize(n*8);
    lz.resize(n*8);
    for(int i = 0; i < n; i++){
        a[i] = {A[i],B[i]};
        upd(1,1,n,a[i].ff,a[i].ss,1);
        swap(a[i].ff,a[i].ss);
    }
    sort(a.begin(),a.end());
    for(int i = 0; i < n; i++){
        swap(a[i].ff, a[i].ss);
    }
    return;
}

int can(int m, int k[]) {
    sort(k,k+m);
    vector <int> vis(n,0);
    lz1 = lz;
    st1 = st;
    int ind = 0;
    for(int i = 0; i < m; i++){
        an = 0;
        fnd(1,1,n,k[i]);
        if(an >= k[i]){
            int cnt = 0;
            for(int j = 0; j < n; j++){
                if(a[j].ff <= k[i] and a[j].ss >= k[i] and vis[j] == 0){
                    cnt++;
                    upd(1,1,n,a[j].ff,a[j].ss,-1);
                    vis[j] = 1;
                }
                if(cnt == k[i]){
                    ind = j+1;
                    break;
                }
            }
        }
        else {
            st = st1;
            lz = lz1;
            return 0;
        }
    }
    st = st1;
    lz = lz1;
    return 1;
}

Compilation message (stderr)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:69:9: warning: variable 'ind' set but not used [-Wunused-but-set-variable]
   69 |     int ind = 0;
      |         ^~~

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