oj.uz

Submission #851710

# Submission time Handle Problem Language Result Execution time Memory
851710 2023-09-20T12:23:18 Z vjudge1 Bubble Sort 2 (JOI18_bubblesort2) C++17
17 / 100
 9000 ms 67024 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=23, 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, int c){
    S_sum[ind]+=c;
    while(ind/=2)
        S_sum[ind]+=c;
}

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]];
    }
    pre();
    for(int k=0;k<q;k++){
        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], 1);
        }
        S.push_back(mx);
        
        for(int i=0;i<n;i++){
            update(s_p+A[i], -1);
        }
        
    }
    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 60 ms 66140 KB Output is correct
2 Correct 142 ms 66204 KB Output is correct
3 Correct 713 ms 66340 KB Output is correct
4 Correct 707 ms 66604 KB Output is correct
5 Correct 707 ms 66360 KB Output is correct
6 Correct 672 ms 66612 KB Output is correct
7 Correct 688 ms 66600 KB Output is correct
8 Correct 716 ms 66352 KB Output is correct
9 Correct 700 ms 66356 KB Output is correct
10 Correct 694 ms 66328 KB Output is correct
11 Correct 704 ms 66332 KB Output is correct
12 Correct 685 ms 66328 KB Output is correct
13 Correct 685 ms 66568 KB Output is correct
14 Correct 686 ms 66568 KB Output is correct
15 Correct 692 ms 66320 KB Output is correct
16 Correct 697 ms 66300 KB Output is correct
17 Correct 683 ms 66312 KB Output is correct
18 Correct 702 ms 66552 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 66140 KB Output is correct
2 Correct 142 ms 66204 KB Output is correct
3 Correct 713 ms 66340 KB Output is correct
4 Correct 707 ms 66604 KB Output is correct
5 Correct 707 ms 66360 KB Output is correct
6 Correct 672 ms 66612 KB Output is correct
7 Correct 688 ms 66600 KB Output is correct
8 Correct 716 ms 66352 KB Output is correct
9 Correct 700 ms 66356 KB Output is correct
10 Correct 694 ms 66328 KB Output is correct
11 Correct 704 ms 66332 KB Output is correct
12 Correct 685 ms 66328 KB Output is correct
13 Correct 685 ms 66568 KB Output is correct
14 Correct 686 ms 66568 KB Output is correct
15 Correct 692 ms 66320 KB Output is correct
16 Correct 697 ms 66300 KB Output is correct
17 Correct 683 ms 66312 KB Output is correct
18 Correct 702 ms 66552 KB Output is correct
19 Execution timed out 9006 ms 67024 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 9031 ms 66392 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 66140 KB Output is correct
2 Correct 142 ms 66204 KB Output is correct
3 Correct 713 ms 66340 KB Output is correct
4 Correct 707 ms 66604 KB Output is correct
5 Correct 707 ms 66360 KB Output is correct
6 Correct 672 ms 66612 KB Output is correct
7 Correct 688 ms 66600 KB Output is correct
8 Correct 716 ms 66352 KB Output is correct
9 Correct 700 ms 66356 KB Output is correct
10 Correct 694 ms 66328 KB Output is correct
11 Correct 704 ms 66332 KB Output is correct
12 Correct 685 ms 66328 KB Output is correct
13 Correct 685 ms 66568 KB Output is correct
14 Correct 686 ms 66568 KB Output is correct
15 Correct 692 ms 66320 KB Output is correct
16 Correct 697 ms 66300 KB Output is correct
17 Correct 683 ms 66312 KB Output is correct
18 Correct 702 ms 66552 KB Output is correct
19 Execution timed out 9006 ms 67024 KB Time limit exceeded
20 Halted 0 ms 0 KB -