답안 #630322

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
630322	2022-08-16T07:47:07 Z	Soul234	Poklon (COCI17_poklon)	C++14	140 / 140	2236 ms	355072 KB

poklon

#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

#	결과	실행 시간	메모리	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