#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] = 0;
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] = lessa[rs] = 0;
return;
}
int V = lessa[ind];
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(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
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;
| ~~~~~~~~~~~~~~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
47180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
104 ms |
66964 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
132 ms |
67272 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
511 ms |
149408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
