oj.uz

Submission #479675

# Submission time Handle Problem Language Result Execution time Memory
479675 2021-10-12T18:45:18 Z nicolaalexandra Floppy (RMI20_floppy) C++14
100 / 100
 101 ms 17352 KB 
#include <bits/stdc++.h>
#define DIM 100010
#include "floppy.h"
using namespace std;

vector <pair<int,int> > events[DIM];

/*
void save_to_floppy (string s){
    bits = s;
    cout<<s<<endl;
}
*/
void read_array (int useless, const vector<int> &a){

    int n = a.size();

    string bits;
    deque <int> d;
    for (int i=1;i<=n;i++){
        while (!d.empty() && a[i-1] > a[d.back()-1]){
            d.pop_back();
            bits += "1";
        }
        d.push_back(i);
        bits += "0";
    }


    save_to_floppy(bits);
}

vector <int> solve_queries (int useless, int n, const string &bits, const vector<int> &a, const vector<int> &b){

    vector <int> ans;

    int m = a.size();
    for (int i=0;i<m;i++){
        //a[i]++, b[i]++;
        events[b[i]+1].push_back(make_pair(a[i]+1,i));

        ans.push_back(0);
    }


    deque <int> d;

    int poz = 1;
    for (int i=0;i<bits.size();i++){
        if (bits[i] == '0'){
            d.push_back(poz);

            /// rezolv toate query uile cu b ul in poz
            for (auto it : events[poz]){
                int a = it.first;

                int st = 0, dr = d.size()-1, sol = 0;
                while (st <= dr){
                    int mid = (st+dr)>>1;
                    if (d[mid] >= a){
                        sol = d[mid];
                        dr = mid-1;
                    } else st = mid+1;
                }

                ans[it.second] = sol - 1;
            }

            poz++;
        } else d.pop_back();
    }

    return ans;
}
/*
int main (){

    ifstream cin ("date.in");
    ofstream cout ("date.out");

    int n,m,i,x,y;

    cin>>n;

    vector <int> a(n,0);
    for (i=0;i<n;i++)
        cin>>a[i];

    cin>>m;
    vector <int> A(m,0);
    vector <int> B(m,0);
    for (i=0;i<m;i++)
        cin>>A[i]>>B[i];


    read_array(0,a);

    vector<int> ans = solve_queries(0,n,bits,A,B);
    for (auto it : ans)
        cout<<it<<"\n";

    return 0;
}
*/

Compilation message

floppy.cpp: In function 'std::vector<int> solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:49:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for (int i=0;i<bits.size();i++){
      |                  ~^~~~~~~~~~~~
stub.cpp: In function 'void run2()':
stub.cpp:101:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  101 |     if (query_answers.size() != M) {
      |         ~~~~~~~~~~~~~~~~~~~~~^~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5404 KB Output is correct
2 Correct 4 ms 5404 KB Output is correct
3 Correct 4 ms 5392 KB Output is correct
4 Correct 4 ms 5468 KB Output is correct
5 Correct 5 ms 5404 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 8116 KB Output is correct
2 Correct 25 ms 8140 KB Output is correct
3 Correct 27 ms 8088 KB Output is correct
4 Correct 28 ms 8088 KB Output is correct
5 Correct 24 ms 8080 KB Output is correct

Subtask #3
72.0 / 72.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 17184 KB Output is correct
2 Correct 90 ms 17252 KB Output is correct
3 Correct 96 ms 17148 KB Output is correct
4 Correct 101 ms 17352 KB Output is correct
5 Correct 97 ms 17312 KB Output is correct