#include "teams.h"
#include <stack>
#include <math.h>
#include <vector>
#include <assert.h>
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 5e5+5;
#define right r
#define left l
#define mid (start+end)/2
struct node {
node *l,*r;
int val;
node() {
l=NULL,r=NULL,val=0;
}
node* build(int start, int end) {
val=0;
if(start!=end) {
l=new node,r=new node,l=l->build(start,mid),r=r->build(mid+1,end);
}
return this;
}
int query(int start, int end, int a, int b) {
if(start>=a && end<=b) return val;
else if(start>b || end<a) return 0;
else return l->query(start,mid,a,b)+r->query(mid+1,end,a,b);
}
node* update(int start, int end, int x, int v) {
node* f=new node;
f->left=left;
f->right=right;
f->val=val+v;
if(start==end) {
return f;
}
else if(x<=mid) {
f->left=left->update(start,mid,x,v);
}
else {
f->right=right->update(mid+1,end,x,v);
}
return f;
}
};
node* root[N];
int A[N],B[N];
int n;
int del[N];
int sz=0;
int dp[N];
void init(int _n, int a[], int b[]) {
n=_n;
vector<pair<int,int>> vt;
for(int i=1;i<=n;i++) {
A[i]=a[i-1];
B[i]=b[i-1];
vt.push_back({A[i],B[i]});
}
sort(vt.begin(),vt.end());
root[0]=new node;root[0]=root[0]->build(1,n);
// cout<<"wow\n";
int preve=0;
for(int i=0;i<n;i++) {
while(preve+1<vt[i].first) {
root[preve+1]=root[preve];
preve++;
// cout<<"donel : "<<preve<<endl;
}
root[vt[i].first]=root[preve]->update(1,n,vt[i].second,1);
preve=vt[i].first;
// cout<<"done : "<<preve<<endl;
}
// cout<<"wow\n";
for(int i=preve+1;i<=n;i++) {
root[i]=root[i-1];
// cout<<"donez : "<<i<<endl;
}
}
// int getUnder(int k, int y) {
// int tot=0;
// for(int i=1;i<=n;i++) {
// if(A[i]<=k && B[i]>=k) tot++;
// }
// for(int i=sz;i>=1;i--) {
// }
// }
// bool fx(int k) {
// return 1;
// }
int getCount(int a, int b) {
int tot=0;
for(int i=1;i<=n;i++) {
if(A[i]>a && A[i]<=b && B[i]>=b) tot++;
}
// return tot;
// cout<<"dot1 :"<<a<<" , "<<b<<"\n";
int h=root[b]->query(1,n,b,n)-root[max(0,a-1)]->query(1,n,b,n);
// cout<<"dot2<< : "<<h<<"\n";
assert(tot==h);
return h;
}
int can(int M, int K[]) {
sort(K,K+M);
vector<pair<int,int>> vt;
for(int i=0;i<M;i++) {
if(vt.size()==0 || vt[vt.size()-1].first!=K[i]) {
vt.push_back({K[i],1});
}
else {
vt[vt.size()-1].second++;
}
}
int n2 = vt.size();
int h=sqrt(n);
// assert(n2<=3*h);
int mini=0;
for(int i=0;i<n2;i++) {
dp[i]=getCount(0,vt[i].first)-vt[i].first*vt[i].second;
for(int j=0;j<i;j++) {
dp[i]=min(dp[i],dp[j]-vt[i].first*vt[i].second+getCount(vt[j].first,vt[i].first));
}
if(dp[i]<0) return 0;
}
return 1;
}
Compilation message
teams.cpp: In function 'int can(int, int*)':
teams.cpp:137:19: warning: conversion to 'int' from 'std::vector<std::pair<int, int> >::size_type {aka long unsigned int}' may alter its value [-Wconversion]
int n2 = vt.size();
^
teams.cpp:138:14: warning: conversion to 'int' from '__gnu_cxx::__enable_if<true, double>::__type {aka double}' may alter its value [-Wfloat-conversion]
int h=sqrt(n);
^
teams.cpp:138:6: warning: unused variable 'h' [-Wunused-variable]
int h=sqrt(n);
^
teams.cpp:140:6: warning: unused variable 'mini' [-Wunused-variable]
int mini=0;
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
13780 KB |
Output is correct |
| 2 |
Correct |
0 ms |
13780 KB |
Output is correct |
| 3 |
Runtime error |
0 ms |
13784 KB |
Execution killed because of forbidden syscall gettid (186) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
136 ms |
77180 KB |
Execution killed because of forbidden syscall gettid (186) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
146 ms |
77180 KB |
Execution killed because of forbidden syscall gettid (186) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
953 ms |
364804 KB |
Execution killed because of forbidden syscall gettid (186) |
| 2 |
Halted |
0 ms |
0 KB |
- |
