oj.uz

답안 #312489

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
312489 2020-10-13T14:18:23 Z knon0501 코끼리 (Dancing Elephants) (IOI11_elephants) C++14
97 / 100
 3613 ms 14200 KB 
#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;
            }
        }
    }
}
void del(int x,int y){
    for(int i=0 ; i<a[x].size() ; i++){
        if(a[x][i].x==y){
            a[x].erase(a[x].begin()+i);
            break;
        }
    }
    for(int i=(int)a[x].size()-1 ; i>=0 ; i--){
        if(a[x][i].x+L>=a[x].rbegin()->x){
            a[x][i].nxt=a[x][i].x+L;
            a[x][i].cnt=1;
        }
        else{
            auto k=upper_bound(a[x].begin(),a[x].end(),(A){a[x][i].x+L,0,0},[&](A q,A w){
                        return q.x<w.x;
                        });
            a[x][i].cnt=k->cnt+1;
            a[x][i].nxt=k->nxt;
        }
    }
}
void add(int x,int y){
    for(int i=0 ; i<=a[x].size() ; i++){
        if(i==a[x].size() || a[x][i].x>=y ){
            a[x].insert(a[x].begin()+i,{y,0,0});
            break;
        }
    }

    for(int i=(int)a[x].size()-1 ; i>=0 ; i--){
        if(a[x][i].x+L>=a[x].rbegin()->x){
            a[x][i].nxt=a[x][i].x+L;
            a[x][i].cnt=1;
        }
        else{
            auto k=upper_bound(a[x].begin(),a[x].end(),(A){a[x][i].x+L,0,0},[&](A q,A w){
                        return q.x<w.x;
                        });
            a[x][i].cnt=k->cnt+1;
            a[x][i].nxt=k->nxt;
        }

     ///    cout<<C<<" "<<a[x][i].x<<" "<<a[x][i].nxt<<" "<<a[x][i].cnt<<endl;
    }
}
int f(){
    int x=-2e9;
    int ans=0;
    for(int i=0 ; i<=(n-1)/t ; i++){
        if(a[i].size()==0 || x>=a[i].rbegin()->x)continue;
        auto k=upper_bound(a[i].begin(),a[i].end(),(A){x,0,0},[&](A q, A w){
                           return q.x<w.x;
                           });
        ans+=k->cnt;
        x=k->nxt;
   ///     cout<<x<<" "<<ans<<"!\n";
    }
    return ans;
}
int g(int x){
    int k=-1;
    for(int i=0 ; i<=(n-1)/t ; i++){
        if (x<=a[i].rbegin()->x ){
        k=i;
        break;}
    }
    if(k>=0)return k;
    return (n-1)/t;
}/*
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cin>>n>>L>>m;
    int i;
    for(i=0 ; i<n ; i++)cin>>b[i];

    for(i=0 ; i<m ; i++)
    {
        if(i%(t-1)==0)init();

        int x,y;
        cin>>x>>y;
        del(g(b[x]),b[x]);
        add(g(y),y);
        b[x]=y;
        cout<<f()<<"\n";
    }
    return 0;
}*/
#include "elephants.h"



void init(int N, int l, int X[])
{
    L=l;
    n=N;
    for(int i=0 ; i<N ; i++)b[i]=X[i];

}

int update(int i, int y)
{
    if(C%(t-1)==0)init();
    C++;
    del(g(b[i]),b[i]);
    add(g(y),y);
    b[i]=y;
    return f();
}

Compilation message

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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1215 ms 1788 KB Output is correct
8 Correct 1380 ms 1912 KB Output is correct
9 Correct 1365 ms 2812 KB Output is correct
10 Correct 1369 ms 2808 KB Output is correct
11 Correct 1225 ms 2808 KB Output is correct
12 Correct 2117 ms 2808 KB Output is correct
13 Correct 1239 ms 2684 KB Output is correct

Subtask #4
47.0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1215 ms 1788 KB Output is correct
8 Correct 1380 ms 1912 KB Output is correct
9 Correct 1365 ms 2812 KB Output is correct
10 Correct 1369 ms 2808 KB Output is correct
11 Correct 1225 ms 2808 KB Output is correct
12 Correct 2117 ms 2808 KB Output is correct
13 Correct 1239 ms 2684 KB Output is correct
14 Correct 962 ms 2040 KB Output is correct
15 Correct 1706 ms 2168 KB Output is correct
16 Correct 3071 ms 3064 KB Output is correct
17 Correct 3613 ms 3704 KB Output is correct
18 Correct 3589 ms 3700 KB Output is correct
19 Correct 2535 ms 3684 KB Output is correct
20 Correct 3595 ms 3716 KB Output is correct
21 Correct 3478 ms 3696 KB Output is correct
22 Correct 2202 ms 3704 KB Output is correct

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1215 ms 1788 KB Output is correct
8 Correct 1380 ms 1912 KB Output is correct
9 Correct 1365 ms 2812 KB Output is correct
10 Correct 1369 ms 2808 KB Output is correct
11 Correct 1225 ms 2808 KB Output is correct
12 Correct 2117 ms 2808 KB Output is correct
13 Correct 1239 ms 2684 KB Output is correct
14 Correct 962 ms 2040 KB Output is correct
15 Correct 1706 ms 2168 KB Output is correct
16 Correct 3071 ms 3064 KB Output is correct
17 Correct 3613 ms 3704 KB Output is correct
18 Correct 3589 ms 3700 KB Output is correct
19 Correct 2535 ms 3684 KB Output is correct
20 Correct 3595 ms 3716 KB Output is correct
21 Correct 3478 ms 3696 KB Output is correct
22 Correct 2202 ms 3704 KB Output is correct
23 Runtime error 106 ms 14200 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Halted 0 ms 0 KB -