oj.uz

Submission #630322

# Submission time Handle Problem Language Result Execution time Memory
630322 2022-08-16T07:47:07 Z Soul234 Poklon (COCI17_poklon) C++14
140 / 140
 2236 ms 355072 KB 
#include<bits/stdc++.h>
using namespace std;

void DBG() { cerr << "]\n"; }
template<class H, class... T> void DBG(H h, T... t) {
    cerr << h; if(sizeof...(t)) cerr << ", ";
    DBG(t...);
}
#ifdef LOCAL
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 0
#endif // LOCAL

#define FOR(i,a,b) for(int i = (a) ; i<(b) ; i++)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for(int i = (b)-1 ; i>=(a) ; i--)
#define R0F(i,a) ROF(i,0,a)
#define each(e,a) for(auto &e : (a))
#define sz(v) (int)(v).size()
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pb push_back
#define tcT template<class T
#define nl "\n"

using ll = long long;
using vi = vector<int>;
using pi = pair<int,int>;
using str = string;
tcT> using V = vector<T>;
tcT> using pqg = priority_queue<T,vector<T>,greater<T>>;

void setIO(string NAME = "") {
    cin.tie(0)->sync_with_stdio(0);
    if(sz(NAME)) {
        freopen((NAME + ".inp").c_str(),"r",stdin);
        freopen((NAME + ".out").c_str(),"w",stdout);
    }
}

tcT> bool ckmin(T&a, const T&b) {
    return b < a ? a=b,1 : 0; }
tcT> bool ckmax(T&a, const T&b) {
    return b > a ? a=b,1 : 0; }

const int MOD = 1e9 + 7;

struct Dat {
    bool isQ;
    int tt, val;
    Dat(bool _isQ = false, int _tt = 0, int _val = 0) {
        isQ = _isQ;
        tt = _tt;
        val = _val;
    }
    bool operator<(const Dat&rhs) const {
        if(tt == rhs.tt) return isQ < rhs.isQ;
        return tt < rhs.tt;
    }
};

const int MX = 5e5+5;
int N, Q, lef[MX], rig[MX], A[MX];

int ans[MX];

map<int,int> lst;

V<Dat> evn[MX*4 + 7];

void insQry(int id, int l, int r, int ind = 1, int L = 1, int R = N) {
    evn[ind].pb(Dat(true, r, id));
    if(L == R) return;
    int mid = (L + R) >> 1;
    if(l <= mid) insQry(id, l, r, ind<<1, L, mid);
    else insQry(id, l, r, ind<<1|1, mid+1, R);
}

void insEle(int lcur, int cur, int rcur, int rrcur, int ind = 1, int L = 1, int R = N) {
    if(L > cur || R < lcur) return;
    if(lcur <= L && R <= cur) {
        evn[ind].pb(Dat(false, rcur, 1));
        evn[ind].pb(Dat(false, rrcur, -1));
        return;
    }
    int mid = (L + R) >> 1;
    insEle(lcur, cur, rcur, rrcur, ind<<1, L, mid);
    insEle(lcur, cur, rcur, rrcur, ind<<1|1, mid+1, R);
}

void calc(int ind = 1, int L = 1, int R = N) {
    sort(all(evn[ind]));
    int cur = 0;
    F0R(i,sz(evn[ind])) {
        if(evn[ind][i].isQ) ans[evn[ind][i].val] += cur;
        else cur += evn[ind][i].val;
    }
    if(L == R) return;
    int mid = (L + R) >> 1;
    calc(ind<<1, L, mid);
    calc(ind<<1|1, mid+1, R);
}

void solve() {
    cin >> N >> Q;
    FOR(i,1,N+1) cin >> A[i];
    FOR(i,1,N+1) {
        int cur;
        if(lst.count(A[i])) cur = lst[A[i]];
        else cur = 0;
        lef[i] = cur;
        lst[A[i]] = i;
    }
    lst.clear();
    ROF(i,1,N+1) {
        int cur;
        if(lst.count(A[i])) cur = lst[A[i]];
        else cur = N+1;
        rig[i] = cur;
        lst[A[i]] = i;
    }
    F0R(i, Q) {
        int L, R;
        cin >> L >> R;
        insQry(i, L, R);
    }
    FOR(i,1,N+1) if(rig[i] <= N) {
        insEle(lef[i]+1, i, rig[i], rig[rig[i]]);
    }
    calc();
    F0R(i, Q) cout << ans[i] << nl;
}

int main() {
    setIO();

    int t=1;
    //cin>>t;
    while(t-->0) {
        solve();
    }

    return 0;
}

Compilation message

poklon.cpp: In function 'void setIO(std::string)':
poklon.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         freopen((NAME + ".inp").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
poklon.cpp:38:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         freopen((NAME + ".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47332 KB Output is correct
2 Correct 23 ms 47488 KB Output is correct
3 Correct 25 ms 47696 KB Output is correct
4 Correct 40 ms 49352 KB Output is correct
5 Correct 336 ms 95840 KB Output is correct
6 Correct 340 ms 98860 KB Output is correct
7 Correct 835 ms 168584 KB Output is correct
8 Correct 1344 ms 236584 KB Output is correct
9 Correct 1778 ms 298396 KB Output is correct
10 Correct 2236 ms 355072 KB Output is correct