oj.uz

Submission #1067464

# Submission time Handle Problem Language Result Execution time Memory
1067464 2024-08-20T17:21:51 Z LeeQuoMing Poklon (COCI17_poklon) C++14
140 / 140
 977 ms 23664 KB 
#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using ll = long long;
using vi = vector<int>;
#define pb push_back
#define bit(mask, i) (((mask)>>(i))&1)
#define all(x) (x).begin(),(x).end()
#define FOR(i, s, e, inc) for(int i = s; i<=e; i+=inc)
#define pi acos(-1)

using pii = pair<int,int>;
#define F first
#define S second
#define MP make_pair

#define dbg_time() cerr<<"Time: "<<1000 * ((double)clock() / (double)CLOCKS_PER_SEC) <<"ms"<<endl;

#define endl '\n';
const ll MOD = (ll)1e9+7;
const int M = 5e5+5;

void setIO(string name = ""){
    if(name.size()){
        freopen((name + ".INP").c_str(), "r", stdin);
        freopen((name + ".OUT").c_str(), "w", stdout);
    }
}
int a[M],b[M], ans[M],n, m, cnt[M],sz=710, cur = 0;

struct query{
    int l, r, id;
} q[M];

void add(int x){ ++cnt[x]; cur += (cnt[x]==2 ? 1 : (cnt[x]==3 ? -1 : 0));}
void del(int x){ --cnt[x]; cur += (cnt[x]==2 ? 1 : (cnt[x]==1 ? -1 : 0));}

int main(){
    fast;
    cin>>n>>m;
    for(int i = 1; i<=n; ++i) cin>>a[i], b[i] = a[i];
    sort(b+1, b+1+n);
    for(int i = 1; i<=n; ++i) 
        a[i] = lower_bound(b+1,b+1+n, a[i]) -b;
    for(int i = 1; i<=m; ++i) cin>>q[i].l>>q[i].r, q[i].id = i;
    sort(q+1, q+1+m, [&](query&a, query&b){     // sort q+1 -> q+1+m
        if(a.l/sz==b.l/sz){
            if(a.l/sz&1)
                return a.r<b.r;
            return a.r<b.r;
        }
        return a.l<b.l;
    });  
    int L = 1, R = 0;
    for(int i = 1; i<=m; ++i){
        while(L<q[i].l) del(a[L++]);
        while(L>q[i].l) add(a[--L]);
        while(R>q[i].r) del(a[R--]);        
        while(R<q[i].r) add(a[++R]);        
        ans[q[i].id] = cur; 
    }
    for(int i = 1; i<=m; ++i) cout<<ans[i]<<endl;
    // dbg_time(); 
    return 0;
}

Compilation message

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

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 4 ms 604 KB Output is correct
5 Correct 87 ms 4616 KB Output is correct
6 Correct 89 ms 4688 KB Output is correct
7 Correct 250 ms 9556 KB Output is correct
8 Correct 457 ms 14164 KB Output is correct
9 Correct 689 ms 18944 KB Output is correct
10 Correct 977 ms 23664 KB Output is correct