Submission #312489

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
312489	2020-10-13 14:18:23	knon0501	Dancing Elephants (IOI11_elephants)	C++14	97 / 100	3613 ms	14200 KiB

elephants

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
int t=350;
int n,L,m;
int b[150000];
int c[150000];
struct A{
    int x,cnt,nxt,idx;
};
vector<A> a[400];
int C;
void init(){
    int i,j;
    for(i=0 ; i<n ; i++)c[i]=b[i];
    sort(c,c+n);
    for(i=0 ; i<=(n-1)/t ; i++)a[i].clear();
    for(i=0 ; i<n  ;i++)
        a[i/t].push_back({c[i],0,0});
    for(i=(n-1)/t ; i>=0 ; i--){
        for(j=(int)a[i].size()-1 ; j>=0 ; j--){
            if(a[i][j].x+L>=a[i].rbegin()->x){
                a[i][j].nxt=a[i][j].x+L;
                a[i][j].cnt=1;
            }
            else{
                auto k=upper_bound(a[i].begin(),a[i].end(),(A){a[i][j].x+L,0,0},[&](A q,A w){
                        return q.x<w.x;
                        });
                a[i][j].cnt=k->cnt+1;
                a[i][j].nxt=k->nxt;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

elephants.cpp: In function 'void del(int, int)':
elephants.cpp:36:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<A>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for(int i=0 ; i<a[x].size() ; i++){
      |                   ~^~~~~~~~~~~~
elephants.cpp: In function 'void add(int, int)':
elephants.cpp:57:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<A>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for(int i=0 ; i<=a[x].size() ; i++){
      |                   ~^~~~~~~~~~~~~
elephants.cpp:58:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<A>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         if(i==a[x].size() || a[x][i].x>=y ){
      |            ~^~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 47 / 47
• Subtask 5: 0 / 3