Submission #541133

#	Time	Username	Problem	Language	Result	Execution time	Memory
541133		lukameladze	Teams (IOI15_teams)	C++17	77 / 100	4088 ms	165644 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define pii pair <int, int>
using namespace std;
const int N = 5e5 + 5;
int tree[30*N],le_[30*N], ri_[30*N];
int cur,root[N],prevroot,dp[N],m,a[N],b[N],k[N],n,cnt;
set <pii> s;
set <int > s1;
vector <int> v[N];
int merge(int a, int b) {
    return a + b;
}
void build(int node, int le, int ri) {
   // cout<<le<<" "<<ri<<" "<<node<<endl;
    if (le == ri) {
        tree[node] = 0;
        return ;
    }
    cur++;
    le_[node] = cur;
    cur++;
    ri_[node] = cur;
    int mid = (le + ri) / 2;
    build(le_[node],le,mid);
    build(ri_[node],mid + 1, ri);
    tree[node] = merge(tree[le_[node]], tree[ri_[node]]);
}
void update(int node, int le, int ri, int idx, int val) {
    if (le > idx || ri < idx) return ;
    
    if (le == ri) {
        tree[cur] = tree[node] + val;
        //cout<<cur<<" "<<le<<" "<<ri<<" "<<tree[cur]<<endl;
        return ;
    }
    int mid = (le + ri) / 2;
    int x = cur;
    cur++;
    le_[x] = le_[node];
    ri_[x] = ri_[node];
    if (idx <= mid) {
        le_[x] = cur;
    } else ri_[x] = cur;
    update(le_[node], le,mid,idx,val);
    update(ri_[node], mid + 1, ri, idx,val);
    tree[x] = merge(tree[le_[x]], tree[ri_[x]]);
    //cout<<x<<" "<<le<<" "<<ri<<" "<<tree[x]<<endl;
}
int getans(int node, int le, int ri, int start, int end) {
    if (le > end || ri < start) return 0;
    if (le >= start && ri <= end) {
        return tree[node];
    }
    int mid = (le + ri) / 2;
    return merge(getans(le_[node],le,mid,start,end), getans(ri_[node],mid + 1,ri,start,end));
}
int F(int lef, int rig) {
    // rig === k[rig]
    return getans(root[rig],1,n,rig,n) - getans(root[lef],1,n,rig,n);
}
int getidx(int a, int b) {
    int le = k[b]+1; 
    int ri = n;
    int ans = 0;
    while (le <= ri) {
        int mid = (le + ri) / 2;
        if (dp[a] - dp[b] < F(k[b],mid) - F(k[a],mid)) {
            ans = mid; ri = mid - 1;
        } else le = mid + 1;
    }
    return ans;
}
void del(int idx) {
   // cout<<idx<<" del"<<endl;
   if (!s1.count(idx)) return ;
    s1.erase(idx);
    if (!s1.size()) return ;
	int prit = -1, nxt = -1;
    if (*s1.begin() < idx) {
    	prit = *(--s1.upper_bound(idx));
	}
    if (s1.upper_bound(idx) != s1.end()) nxt = *(s1.upper_bound(idx));
    int xx;
	if (nxt != -1) {
       xx = getidx(idx,nxt);
       if (xx) s.erase({xx,nxt});
	}
	if (prit != -1) {
		xx = getidx(prit, idx);
		if (xx) s.erase({xx,idx});
		if (nxt != -1) {
		    xx = getidx(prit,nxt);
		    if (xx)
		    s.insert({xx,nxt});
		}
	}
}
void add(int idx) {
    //cout<<idx<<" add"<<endl;
    s1.insert(idx);
    if (!s1.size()) return ;
    int prit = -1, nxt = -1;
    int xx;
    if (*s1.begin() < idx) {
        prit = *(--s1.lower_bound(idx));
    }
    if (s1.upper_bound(idx) != s1.end()) {
        nxt = *s1.upper_bound(idx);
    }
    //cout<<prit<<" "<<nxt<<endl;
    if (prit != -1 && nxt != -1) {
        xx = getidx(prit, nxt);
        if (xx) s.erase({xx,nxt});
    }
    if (prit != -1) {
        xx = getidx(prit,idx);
        if (xx) s.insert({xx,idx});//;, cout<<"add "<<xx<<" "<<prit<<" "<<idx<<endl;
    }
    if (nxt != -1) {
        xx = getidx(idx, nxt);
        if (xx) s.insert({xx,nxt});//, cout<<"add "<<xx<<" "<<nxt<<endl;
    }
    
}
int can(int M, int K[]) {
    s.clear();
    s1.clear();
	m = M;
	for (int i = 1; i <= m; i++) {
		dp[i] = 0;
		k[i] = K[i - 1];
	}
	int sum = 0;
    for (int i = 1; i <= m; i++) {
        sum += k[i];
    }
    if (sum > n) {
        return 0;
    }
    sort(k + 1, k + m + 1);
	dp[0] = 0;
	add(0);
	for (int i = 1; i <= m; i++) dp[i] = 1e9;
	 for (int i = 1; i <= m; i++) {
	     // rodis waishleba    index
	     while (s.size()) {
	         multiset < pii > :: iterator it = s.begin();
	         if ((*it).f <= k[i]) {
	             int todel = (*it).s;
	             del(todel);
	         }
	         else break;
	     }
	     int id = *(--s1.end());
	     dp[i] = dp[id] + F(k[id],k[i]) - k[i];
	     //cout<<i<<" "<<id<<" "<<dp[i]<<endl;
	     if (dp[i] < 0) return 0;
	     add(i);
	     /*
        for (int j = i - 1; j >= 0; j--) {
            // k[j]+1 -----> k[i] shualedshi >= k[i] 
            cnt = getans(root[k[i]],1,n,k[i],n) - getans(root[k[j]],1,n,k[i],n);
            dp[i] = min(dp[i],dp[j] + cnt - k[i]);
           // cout<<i<<" "<<j<<" "<<dp[j]<<" "<<cnt<<endl;
             //cout<<i<<"   "<<dp[i]<<endl;
            if (dp[i] < 0) {
                return 0;
            }
        }*/
        //cout<<i<<" "<<dp[i]<<endl;
    }
    return 1;
}
void init(int N, int A[], int B[]) {
	n = N;
    for (int i = 1; i <= n; i++) {
        a[i] = A[i - 1]; b[i] = B[i - 1];
        v[a[i]].pb(b[i]);
    }
    
    cur = 1; root[0] = 1;
    build(1,1,n); 
    for (int i = 1; i <= n; i++) {
        prevroot = root[i - 1];
        root[i] = root[i - 1];
        for (int j = 0; j < v[i].size(); j++) {
            cur++;
            root[i] = cur;
            update(prevroot, 1,n,v[i][j],1);
            prevroot = root[i];
        }
    }
    dp[0] = 0;
   
}

Compilation message (stderr)

teams.cpp: In function 'int merge(int, int)':
teams.cpp:14:22: warning: declaration of 'b' shadows a global declaration [-Wshadow]
   14 | int merge(int a, int b) {
      |                  ~~~~^
teams.cpp:10:39: note: shadowed declaration is here
   10 | int cur,root[N],prevroot,dp[N],m,a[N],b[N],k[N],n,cnt;
      |                                       ^
teams.cpp:14:15: warning: declaration of 'a' shadows a global declaration [-Wshadow]
   14 | int merge(int a, int b) {
      |           ~~~~^
teams.cpp:10:34: note: shadowed declaration is here
   10 | int cur,root[N],prevroot,dp[N],m,a[N],b[N],k[N],n,cnt;
      |                                  ^
teams.cpp: In function 'int getidx(int, int)':
teams.cpp:65:23: warning: declaration of 'b' shadows a global declaration [-Wshadow]
   65 | int getidx(int a, int b) {
      |                   ~~~~^
teams.cpp:10:39: note: shadowed declaration is here
   10 | int cur,root[N],prevroot,dp[N],m,a[N],b[N],k[N],n,cnt;
      |                                       ^
teams.cpp:65:16: warning: declaration of 'a' shadows a global declaration [-Wshadow]
   65 | int getidx(int a, int b) {
      |            ~~~~^
teams.cpp:10:34: note: shadowed declaration is here
   10 | int cur,root[N],prevroot,dp[N],m,a[N],b[N],k[N],n,cnt;
      |                                  ^
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:178:15: warning: declaration of 'N' shadows a global declaration [-Wshadow]
  178 | void init(int N, int A[], int B[]) {
      |           ~~~~^
teams.cpp:8:11: note: shadowed declaration is here
    8 | const int N = 5e5 + 5;
      |           ^
teams.cpp:190:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  190 |         for (int j = 0; j < v[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~

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