oj.uz

Submission #851699

# Submission time Handle Problem Language Result Execution time Memory
851699 2023-09-20T11:47:10 Z vjudge1 Bubble Sort 2 (JOI18_bubblesort2) C++17
38 / 100
 9000 ms 2192 KB 
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif
 
// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
 
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
//#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define FF first
#define SS second
#define all(a) a.begin(), a.end()
#define mod (ll)(1000000007)
int pr=15, s_p=1<<pr, e_p=(1<<(pr+1))-1;
int n;
vector<int>S_sum;

void pre(){
    S_sum.clear();
    S_sum.resize(1<<(pr+1));
}

void update(int ind){
    S_sum[ind]++;
    while(ind/=2)
        S_sum[ind]++;
}

int get(int id, int u, int v, int l, int r){
    if(l>v || r<u)
        return 0;
    if(l>=u && r<=v)
        return S_sum[id];
    int md=(l+r)/2;
    return get(id*2, u, v, l, md)+get(id*2+1, u, v, md+1, r);
}

vector<int> countScans(vector<int>A, vector<int>X, vector<int>V){
    vector<int>S, All;
    n=A.size();
    int q=X.size();
    for(int i=0;i<n;i++){
        All.push_back(A[i]);
    }
    for(int i=0;i<q;i++){
        All.push_back(V[i]);
    }
    sort(all(All));
    int cur=1;
    map<int, int>mp;
    for(int i=0;i<All.size();i++){
        if(i==All.size()-1 || All[i]!=All[i+1])
            mp[All[i]]=cur++;
    }
    for(int i=0;i<n;i++){
        A[i]=mp[A[i]];
    }
    for(int k=0;k<q;k++){
        pre();
        A[X[k]]=mp[V[k]];
        int mx=0;
        for(int i=0;i<n;i++){
            int cur=get(1, s_p+A[i]+1, e_p, s_p, e_p);
            mx=max(mx, cur);
            update(s_p+A[i]);
        }
        S.push_back(mx);
    }
    return S;
}

//int main(){
//    ios_base::sync_with_stdio(0);cin.tie(0);
//    int n, q;
//    cin>>n>>q;
//    vector<int>A(n), X(q), V(q);
//    for(int i=0;i<n;i++){
//        cin>>A[i];
//    }
//    for(int j=0;j<q;j++){
//        cin>>X[j]>>V[j];
//    }
//    vector<int>Ans=countScans(A, X, V);
//    for(int i=0;i<q;i++){
//        cout<<Ans[i]<<endl;
//    }
//}

Compilation message

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:145:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |     for(int i=0;i<All.size();i++){
      |                 ~^~~~~~~~~~~
bubblesort2.cpp:146:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |         if(i==All.size()-1 || All[i]!=All[i+1])
      |            ~^~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 600 KB Output is correct
2 Correct 77 ms 812 KB Output is correct
3 Correct 446 ms 1112 KB Output is correct
4 Correct 437 ms 984 KB Output is correct
5 Correct 424 ms 1112 KB Output is correct
6 Correct 369 ms 1000 KB Output is correct
7 Correct 395 ms 856 KB Output is correct
8 Correct 405 ms 996 KB Output is correct
9 Correct 438 ms 1104 KB Output is correct
10 Correct 392 ms 864 KB Output is correct
11 Correct 390 ms 856 KB Output is correct
12 Correct 396 ms 968 KB Output is correct
13 Correct 400 ms 1112 KB Output is correct
14 Correct 392 ms 932 KB Output is correct
15 Correct 402 ms 948 KB Output is correct
16 Correct 391 ms 936 KB Output is correct
17 Correct 398 ms 928 KB Output is correct
18 Correct 392 ms 1180 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 600 KB Output is correct
2 Correct 77 ms 812 KB Output is correct
3 Correct 446 ms 1112 KB Output is correct
4 Correct 437 ms 984 KB Output is correct
5 Correct 424 ms 1112 KB Output is correct
6 Correct 369 ms 1000 KB Output is correct
7 Correct 395 ms 856 KB Output is correct
8 Correct 405 ms 996 KB Output is correct
9 Correct 438 ms 1104 KB Output is correct
10 Correct 392 ms 864 KB Output is correct
11 Correct 390 ms 856 KB Output is correct
12 Correct 396 ms 968 KB Output is correct
13 Correct 400 ms 1112 KB Output is correct
14 Correct 392 ms 932 KB Output is correct
15 Correct 402 ms 948 KB Output is correct
16 Correct 391 ms 936 KB Output is correct
17 Correct 398 ms 928 KB Output is correct
18 Correct 392 ms 1180 KB Output is correct
19 Correct 5736 ms 1800 KB Output is correct
20 Correct 7600 ms 1940 KB Output is correct
21 Correct 6561 ms 1940 KB Output is correct
22 Correct 7295 ms 2192 KB Output is correct
23 Correct 6642 ms 2044 KB Output is correct
24 Correct 6640 ms 1884 KB Output is correct
25 Correct 6661 ms 1992 KB Output is correct
26 Correct 6583 ms 2128 KB Output is correct
27 Correct 6626 ms 1916 KB Output is correct
28 Correct 6602 ms 1692 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5193 ms 1176 KB Output is correct
2 Execution timed out 9097 ms 2004 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 600 KB Output is correct
2 Correct 77 ms 812 KB Output is correct
3 Correct 446 ms 1112 KB Output is correct
4 Correct 437 ms 984 KB Output is correct
5 Correct 424 ms 1112 KB Output is correct
6 Correct 369 ms 1000 KB Output is correct
7 Correct 395 ms 856 KB Output is correct
8 Correct 405 ms 996 KB Output is correct
9 Correct 438 ms 1104 KB Output is correct
10 Correct 392 ms 864 KB Output is correct
11 Correct 390 ms 856 KB Output is correct
12 Correct 396 ms 968 KB Output is correct
13 Correct 400 ms 1112 KB Output is correct
14 Correct 392 ms 932 KB Output is correct
15 Correct 402 ms 948 KB Output is correct
16 Correct 391 ms 936 KB Output is correct
17 Correct 398 ms 928 KB Output is correct
18 Correct 392 ms 1180 KB Output is correct
19 Correct 5736 ms 1800 KB Output is correct
20 Correct 7600 ms 1940 KB Output is correct
21 Correct 6561 ms 1940 KB Output is correct
22 Correct 7295 ms 2192 KB Output is correct
23 Correct 6642 ms 2044 KB Output is correct
24 Correct 6640 ms 1884 KB Output is correct
25 Correct 6661 ms 1992 KB Output is correct
26 Correct 6583 ms 2128 KB Output is correct
27 Correct 6626 ms 1916 KB Output is correct
28 Correct 6602 ms 1692 KB Output is correct
29 Correct 5193 ms 1176 KB Output is correct
30 Execution timed out 9097 ms 2004 KB Time limit exceeded
31 Halted 0 ms 0 KB -