oj.uz

Submission #482391

# Submission time Handle Problem Language Result Execution time Memory
482391 2021-10-24T10:12:28 Z Carmel_Ab1 Index (COCI21_index) C++17
60 / 110
 2500 ms 325696 KB 
#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 vector<pi> vpi;

//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);cout.tie(NULL)
#define print(x){for(auto ait:x) cout << ait << " "; cout << "\n";}
#define pb push_back
#define umap unordered_map

template<typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) {
    is >> p.first >> p.second;
    return is;
}

template<typename T1, typename T2>
ostream &operator<<(ostream &os, pair<T1, T2> &p) {
    os << "" << p.first << " " << p.second << "";
    return os;
}

void usaco(string taskname) {
    string fin = taskname + ".in";
    string fout = taskname + ".out";
    const char *FIN = fin.c_str();
    const char *FOUT = fout.c_str();
    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);
}

template<typename T>
void read(vector<T> &v) {
    int n = v.size();
    for (int i = 0; i < n; i++)
        cin >> v[i];
}

template<typename T>
vector<T> UNQ(vector<T> a) {
    vector<T> ans;
    for (T t: a)
        if (ans.empty() || t != ans.back())
            ans.push_back(t);
    return ans;
}

ll ceil(ll a, ll b) {
    ll ans = a / b;
    if (a % b)ans++;
    return ans;
}

ld log(ld a, ld b) { return log(b) / log(a); }

ll power(ll base, ll exp, ll M = 1e18) {//(base^exp)%M
    ll ans = 1;
    while (exp) {
        if (exp % 2 == 1)ans = ((ans % M) * (base % M)) % M;
        base = ((base % M) * (base % M)) % M;
        exp /= 2;
    }
    return ans;
}

string to_base(int n, int new_base) {
    string s;
    int nn = n;
    while (nn) {
        s += to_string(nn % new_base);
        nn /= new_base;
    }
    reverse(all(s));
    return s;
}

ll gcd(ll a, ll b) {
    if (a < b)swap(a, b);
    if (b == 0)return a;
    return gcd(b, a % b);
}

ll lcm(ll a, ll b) {
    ll x = (a / gcd(a, b));
    return b * x;
}

vl generate_array(ll n, ll mn = 1, ll mx = 1e18 + 1) {
    if (mx == 1e18 + 1)
        mx = n;
    vl ans(n);
    for (int i = 0; i < n; i++)
        ans[i] = (mn + rand() % (mx - mn + 1));
    return ans;
}

string substr(string s, int l, int r) {
    string ans;
    for (int i = l; i <= r; i++)
        ans += s[i];
    return ans;
}


void solve();

int main() {
    GLHF;
    int t = 1;
    //cin >> t;
    while (t--)
        solve();
}
struct Seg{
    int l,r,m;
    Seg *lp,*rp;
    int sum=0;

    Seg(int l,int r):l(l),r(r),m((l+r)/2){
        if(l+1<r){
            lp=new Seg(l,m);
            rp=new Seg(m,r);
        }
    }

    Seg* update(int i){
        Seg *ans=new Seg(*this);
        ans->sum++;
        if(l+1==r)
            return ans;

        else if(i<m)
            ans->lp=lp->update(i);
        else
            ans->rp=rp->update(i);
        return ans;
    }

    int query(int a,int b){
        if(b<=l || r<=a)
            return 0;
        else if(a<=l && r<=b)
            return sum;
        else
            return lp->query(a,b)+rp->query(a,b);
    }
};
void solve() {
    int n, q;
    cin >> n >> q;

    vi a(n);

    read(a);

    const int maxai=2e5+2;

    vvi who(maxai);
    for(int i=0; i<n; i++)
        who[a[i]].pb(i);
    vector<Seg*>roots(maxai);
    roots[maxai-1]=new Seg(0,n+3);
    for(int i=maxai-2; 1<=i; i--){
        roots[i]=roots[i+1]->update(n+2);
        for(int j:who[i])
            roots[i]=roots[i]->update(j);
    }

    vvi qs;
    for(int i=0; i<q; i++){
        int l,r;
        cin >> l >> r;
        qs.pb({l-1,r-1,i});
    }
    sort(all(qs),[](vi v1,vi v2){
        return v1[1]<v2[1];
    });

    vi ans(q);

    for(int i=0,j=0; i<n; i++){

        while(j<q && qs[j][1]==i){
            int ix=qs[j][2],l=qs[j][0],r=qs[j][1];

            int li=1,ri=r-l+1,ansc=-1;

            while(li<=ri){
                int mi=(li+ri)/2;
                int has=roots[mi]->query(l,r+1);
                if(has>=mi)
                    ansc=mi,li=mi+1;
                else
                    ri=mi-1;
            }
            ans[ix]=ansc;
            j++;
        }

    }

    for(int i=0; i<q; i++)
        cout << ans[i] << "\n";
}

Compilation message

index.cpp: In function 'void usaco(std::string)':
index.cpp:57:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |     freopen(FIN, "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~
index.cpp:58:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |     freopen(FOUT, "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 110532 KB Output is correct
2 Correct 93 ms 110492 KB Output is correct
3 Correct 151 ms 110568 KB Output is correct
4 Correct 95 ms 110532 KB Output is correct
5 Correct 91 ms 110572 KB Output is correct
6 Correct 140 ms 110560 KB Output is correct
7 Correct 94 ms 110588 KB Output is correct
8 Correct 100 ms 110516 KB Output is correct
9 Correct 95 ms 110572 KB Output is correct
10 Correct 94 ms 110532 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 110532 KB Output is correct
2 Correct 93 ms 110492 KB Output is correct
3 Correct 151 ms 110568 KB Output is correct
4 Correct 95 ms 110532 KB Output is correct
5 Correct 91 ms 110572 KB Output is correct
6 Correct 140 ms 110560 KB Output is correct
7 Correct 94 ms 110588 KB Output is correct
8 Correct 100 ms 110516 KB Output is correct
9 Correct 95 ms 110572 KB Output is correct
10 Correct 94 ms 110532 KB Output is correct
11 Correct 1648 ms 215292 KB Output is correct
12 Correct 709 ms 215400 KB Output is correct
13 Correct 624 ms 215288 KB Output is correct
14 Correct 548 ms 215340 KB Output is correct
15 Correct 554 ms 215288 KB Output is correct
16 Correct 569 ms 215368 KB Output is correct
17 Correct 615 ms 215332 KB Output is correct
18 Correct 578 ms 215292 KB Output is correct
19 Correct 579 ms 215268 KB Output is correct
20 Correct 558 ms 215344 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 110532 KB Output is correct
2 Correct 93 ms 110492 KB Output is correct
3 Correct 151 ms 110568 KB Output is correct
4 Correct 95 ms 110532 KB Output is correct
5 Correct 91 ms 110572 KB Output is correct
6 Correct 140 ms 110560 KB Output is correct
7 Correct 94 ms 110588 KB Output is correct
8 Correct 100 ms 110516 KB Output is correct
9 Correct 95 ms 110572 KB Output is correct
10 Correct 94 ms 110532 KB Output is correct
11 Correct 1648 ms 215292 KB Output is correct
12 Correct 709 ms 215400 KB Output is correct
13 Correct 624 ms 215288 KB Output is correct
14 Correct 548 ms 215340 KB Output is correct
15 Correct 554 ms 215288 KB Output is correct
16 Correct 569 ms 215368 KB Output is correct
17 Correct 615 ms 215332 KB Output is correct
18 Correct 578 ms 215292 KB Output is correct
19 Correct 579 ms 215268 KB Output is correct
20 Correct 558 ms 215344 KB Output is correct
21 Execution timed out 2593 ms 325696 KB Time limit exceeded
22 Halted 0 ms 0 KB -