oj.uz

Submission #257919

# Submission time Handle Problem Language Result Execution time Memory
257919 2020-08-05T04:51:19 Z 문홍윤(#5065) Employment (JOI16_employment) C++17
0 / 100
 5000 ms 4972 KB 
#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define svec(x) sort(x.begin(), x.end())
using namespace std;
typedef pair<int, int> pii;
const int BUC=500;
const int MAXN=200000;
const int INF=1000000001;

int n, q, b;
int arr[MAXN+10];
vector<pair<pii, pii> > vc[MAXN/BUC+10];
vector<pii> sor[MAXN/BUC+10];
int ch[MAXN+100000];

void get_vc(int bnum){
    vc[bnum].clear();
    vc[bnum].eb(mp(0, 0), mp(0, 0));
    for(int i=max(bnum*BUC-1, 0); i<=(bnum+1)*BUC; i++)ch[i]=0;
    int num=0;
    for(int i=0; i<sor[bnum].size(); i++){
        int nw=sor[bnum][i].S;
        ch[nw]=1;
        num++;
        if(nw>0&&ch[nw-1])num--;
        if(ch[nw+1])num--;
        if(i==sor[bnum].size()-1||sor[bnum][i+1].F!=sor[bnum][i].F){
            vc[bnum].eb(mp(sor[bnum][i].F, num), mp(ch[bnum*BUC], ch[(bnum+1)*BUC-1]));
        }
    }
}

pair<int, pii> query2(int bnum, int num){
    for(int i=0; i<vc[bnum].size(); i++){
        if(i==vc[bnum].size()-1||vc[bnum][i+1].F.F>num)
            return mp(vc[bnum][i].F.S, vc[bnum][i].S);
    }
}

int query(int num){
    int on=0, ans=0;
    for(int i=0; i<=b; i++){
        pair<int, pii> tmp=query2(i, num);
        ans+=tmp.F;
        if(on&&tmp.S.F)ans--;
        on=tmp.S.S;
    }
    return ans;
}

void update(int bnum, int a, int b){
    bool flg=false;
    for(int i=0; i<sor[bnum].size(); i++){
        if(sor[bnum][i]==mp(arr[a], a))flg=true;
        if(i==sor[bnum].size()-1||sor[bnum][i+1].F>=b){
            sor[bnum][i]=mp(b, a);
            break;
        }
        if(flg)swap(sor[bnum][i], sor[bnum][i+1]);
    }
    assert(flg);
    arr[a]=b;
    get_vc(bnum);
}

int main(){
    scanf("%d %d", &n, &q);
    for(int i=0; i<n; i++){
        scanf("%d", &arr[i]);
        arr[i]=INF-arr[i];
    }
    b=(n-1)/BUC;
    for(int i=0; i<n; i++)sor[i/BUC].eb(arr[i], i);
    for(int i=0; i<=b; i++)svec(sor[i]);
    for(int i=0; i<=b; i++)get_vc(i);
    for(int i=1; i<=q; i++){
        int qnum;
        scanf("%d", &qnum);
        if(qnum==1){
            int a;
            scanf("%d", &a);
            printf("%d\n", query(INF-a));
        }
        else{
            int a, b;
            scanf("%d %d", &a, &b);
            a--;
            update(a/BUC, a, INF-b);
        }
    }
}

Compilation message

employment.cpp: In function 'void get_vc(int)':
employment.cpp:24:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<sor[bnum].size(); i++){
                  ~^~~~~~~~~~~~~~~~~
employment.cpp:30:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(i==sor[bnum].size()-1||sor[bnum][i+1].F!=sor[bnum][i].F){
            ~^~~~~~~~~~~~~~~~~~~~
employment.cpp: In function 'std::pair<int, std::pair<int, int> > query2(int, int)':
employment.cpp:37:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<vc[bnum].size(); i++){
                  ~^~~~~~~~~~~~~~~~
employment.cpp:38:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(i==vc[bnum].size()-1||vc[bnum][i+1].F.F>num)
            ~^~~~~~~~~~~~~~~~~~~
employment.cpp: In function 'void update(int, int, int)':
employment.cpp:56:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<sor[bnum].size(); i++){
                  ~^~~~~~~~~~~~~~~~~
employment.cpp:58:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(i==sor[bnum].size()-1||sor[bnum][i+1].F>=b){
            ~^~~~~~~~~~~~~~~~~~~~
employment.cpp: In function 'std::pair<int, std::pair<int, int> > query2(int, int)':
employment.cpp:41:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
employment.cpp: In function 'int main()':
employment.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &q);
     ~~~~~^~~~~~~~~~~~~~~~~
employment.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &arr[i]);
         ~~~~~^~~~~~~~~~~~~~~
employment.cpp:81:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &qnum);
         ~~~~~^~~~~~~~~~~~~
employment.cpp:84:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &a);
             ~~~~~^~~~~~~~~~
employment.cpp:89:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d", &a, &b);
             ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 144 ms 888 KB Output is correct
5 Correct 542 ms 1776 KB Output is correct
6 Correct 1113 ms 2040 KB Output is correct
7 Correct 2751 ms 3436 KB Output is correct
8 Correct 4189 ms 4008 KB Output is correct
9 Execution timed out 5061 ms 4972 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -