Submission #470660

#	Time	Username	Problem	Language	Result	Execution time	Memory
470660		Carmel_Ab1	Floppy (RMI20_floppy)	C++17	28 / 100	1088 ms	5764 KiB

floppy

#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//using namespace __gnu_pbds;
using namespace std;

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<pl> vpl;
typedef vector<ld> vld;
typedef pair<ld, ld> pld;

//typedef tree<ll, null_type, less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
template<typename T>
ostream &operator<<(ostream &os, vector<T> &a) {
    os << "[";
    for (int i = 0; i < ll(a.size()); i++) { os << a[i] << ((i != ll(a.size() - 1) ? " " : "")); }
    os << "]\n";
    return os;
}

#define all(x) x.begin(),x.end()
#define YES out("YES")
#define NO out("NO")
#define out(x){cout << x << "\n"; return;}
#define GLHF ios_base::sync_with_stdio(false); cin.tie(NULL)
#define print(x){for(auto ait:x) cout << ait << " "; cout << "\n";}
#define pb push_back
#define umap unordered_map

#include "floppy.h"
//#include "grader.cpp"
string to_base(int n,int b){
    string ans;
    while(n){
        ans+=to_string(n%b);
        n/=b;
    }
    reverse(all(ans));
    return ans;
}
void read_array(int subtask_id, const vi &v) {
    vi so(v);
    sort(all(so));
    map<int,int>conv;
    int n=v.size();
    for(int i=0; i<n; i++)
        conv[so[i]]=i;
    string ans;
    for(int i=0; i<n; i++){
        string s=to_base(conv[v[i]],2);
        while(s.size()!=14)
            s='0'+s;
        ans+=s;
    }
    save_to_floppy(ans);
}
struct seg{
    int sz=1;
    vpl t;
    vl a;
    seg(vl A){
        int n=A.size();
        while(sz<=2*n)
            sz*=2;
        t.resize(sz);
        a.resize(n);
    }
    void update(int i,int v){
        a[i]=v;
        i+=sz/2;
        t[i]={v,i-sz/2};
        while(i){
            pl p1=t[i],p2=t[i^1];
            pl ans={max(p1.first,p2.first),-1};
            if(p1.first>p2.first)
                ans.second=p1.second;
            else
                ans.second=p2.second;
            t[i/2]=ans;
            i/=2;
        }
    }
    int query(int l,int r){
        int ans=l;
        for(l+=sz/2,r+=sz/2 +1; l<r; l/=2,r/=2){
            if(l&1){
                if(t[l].first>a[ans])
                    ans=t[l].second;
                l++;
            }
            if(r&1){
                r--;
                if(t[r].first>a[ans])
                    ans=t[r].second;
            }
        }
        return ans;
    }
};
std::vector<int> solve_queries(int subtask_id, int n,
                               const std::string &bits,
                               const std::vector<int> &l, const std::vector<int> &r){
    vl a(n);
    for(int i=0; i<n; i++)
        a[i]=stoi(bits.substr(14*i,14),0,2);
    seg s(a);
    vi ans;
    for(int i=0; i<n; i++)
        s.update(i,a[i]);
    for(int i=0; i<l.size(); i++)
        ans.pb(s.query(l[i],r[i]));
    return ans;
}

Compilation message (stderr)

floppy.cpp: In function 'std::vector<int> solve_queries(int, int, const string&, const std::vector<int>&, const std::vector<int>&)':
floppy.cpp:119:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |     for(int i=0; i<l.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 / 7
• Subtask 2: 21 / 21
• Subtask 3: 0 / 72