Submission #396388

#TimeUsernameProblemLanguageResultExecution timeMemory
396388peuchTeams (IOI15_teams)C++17
0 / 100
3589 ms141500 KiB
#include "teams.h" #include<bits/stdc++.h> using namespace std; const int MAXN = 5e5 + 10; int n; pair<int, int> v[MAXN]; int bank[MAXN]; int m; int k[MAXN]; vector<int> seg, e, d; int create(); int copia(int pos); int update(int pos, int ini, int fim, int id); int query(int pos, int ini, int fim, int p, int q); void init(int N, int A[], int B[]) { n = N; create(); bank[0] = create(); for(int i = 0; i < n; i++) v[i + 1] = make_pair(A[i], B[i]); sort(v + 1, v + 1 + n); for(int i = 1; i <= n; i++) bank[i] = update(bank[i - 1], 1, n, v[i].second); } int can(int M, int K[]) { m = M; for(int i = 0; i < m; i++) k[i + 1] = K[i]; sort(k + 1, k + 1 + m); stack<pair<int, pair<int, int> > > pilha; pilha.push(make_pair(MAXN + 10, make_pair(0, 0))); for(int i = 1; i <= m; i++){ int j = upper_bound(v + 1, v + 1 + n, make_pair(k[i], MAXN + 10)) - v - 1; if(j <= 0) return 0; while(k[i] > pilha.top().first) pilha.pop(); int sum = query(bank[j], 1, n, k[i], k[i]) - query(bank[pilha.top().second.first], 1, n, k[i], k[i]); int hmin = k[i] + 1; int hmax = k[i]; while(!pilha.empty()){ if(sum >= k[i]) break; int it = pilha.top().second.first; hmax = pilha.top().first; int diff = query(bank[j], 1, n, hmin, hmax) - query(bank[it], 1, n, hmin, hmax); if(diff + sum >= k[i]){ int ini = hmin, fim = hmax; while(ini != fim){ int mid = (ini + fim) >> 1; diff = query(bank[j], 1, n, hmin, mid) - query(bank[it], 1, n, hmin, mid); if(sum + diff >= k[i]) fim = mid; else ini = mid + 1; } hmax = ini; sum += diff; break; } else sum += diff + pilha.top().second.second, hmin = hmax + 1, pilha.pop(); } if(sum < k[i]) return 0; pilha.push(make_pair(hmax, make_pair(j, sum - k[i]))); } return 1; } int create(){ seg.push_back(0); e.push_back(0); d.push_back(0); return seg.size() - 1; } int copia(int pos){ seg.push_back(seg[pos]); e.push_back(e[pos]); d.push_back(d[pos]); return seg.size() - 1; } int update(int pos, int ini, int fim, int id){ if(ini > id || fim < id) return pos; int newNode = copia(pos); if(ini == fim){ seg[newNode]++; return newNode; } int mid = (ini + fim) >> 1; int aux = update(e[pos], ini, mid, id); e[newNode] = aux; aux = update(d[pos], mid + 1, fim, id); d[newNode] = aux; seg[newNode] = seg[e[newNode]] + seg[d[newNode]]; return newNode; } int query(int pos, int ini, int fim, int p, int q){ if(ini > q || fim < p) return 0; if(ini >= p && fim <= q) return seg[pos]; int mid = (ini + fim) >> 1; return query(e[pos], ini, mid, p, q) + query(d[pos], mid + 1, fim, p, q); }

Compilation message (stderr)

teams.cpp: In function 'int can(int, int*)':
teams.cpp:43:73: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
   43 |   int j = upper_bound(v + 1, v + 1 + n, make_pair(k[i], MAXN + 10)) - v - 1;
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
teams.cpp: In function 'int create()':
teams.cpp:83:20: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   83 |  return seg.size() - 1;
      |         ~~~~~~~~~~~^~~
teams.cpp: In function 'int copia(int)':
teams.cpp:90:20: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   90 |  return seg.size() - 1;
      |         ~~~~~~~~~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...