Submission #874135

#	Time	Username	Problem	Language	Result	Execution time	Memory
874135		8pete8	Poklon (COCI17_poklon)	C++14	140 / 140	1014 ms	32964 KiB

poklon

#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include<bitset>
#include <iomanip>  
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<pii,int>
#define vi vector<int>
#define pb push_back
//#define p push
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
#pragma GCC optimize ("03,unroll-lopps")
#define int long long
#define double long double
const int mxn=5e5,inf=1e9;
int cnt[mxn+10],out[mxn+10],root=250,n,q;
pii v[mxn+10];
bool cmp(ppii a,ppii b){return a.f.s<b.f.s;}
void solve(vector<ppii>g){
    if(g.empty())return;
    sort(all(g),cmp);
    int l=g[0].f.f-1,r=l+1,ans=0;
    for(int i=0;i<=n;i++)cnt[i]=0;
    for(auto i:g){
        while(r<=i.f.s){
            cnt[v[r].s]++;
            if(cnt[v[r].s]==2)ans++;
            if(cnt[v[r].s]==3)ans--;
            r++;
        }
        while(l>i.f.f-1){
            cnt[v[l].s]++;
            if(cnt[v[l].s]==2)ans++;
            if(cnt[v[l].s]==3)ans--;
            l--;
        }
        while(l<i.f.f-1){
            l++;
            cnt[v[l].s]--;
            if(cnt[v[l].s]==1)ans--;
            if(cnt[v[l].s]==2)ans++;
            if(l==i.f.f-1)break;
        }
        out[i.s]=ans;
    }
}
int32_t main(){
    fastio
    cin>>n>>q;
    vector<int>pos(n);
    root=sqrt(n*(log2(n)));
    for(int i=0;i<n;i++)cin>>v[i].f,pos[i]=v[i].f;
    sort(all(pos));
    for(int i=0;i<n;i++)v[i].s=lb(all(pos),v[i].f)-pos.begin();
    vector<ppii>qry(q);
    for(int i=0;i<q;i++){
        cin>>qry[i].f.f>>qry[i].f.s,qry[i].s=i;
        qry[i].f.f--;
        qry[i].f.s--;
    }
    sort(all(qry));
    int cur=0;
    for(int i=0;i<n;i+=root){
        vector<ppii>tmp;
        while(qry[cur].f.f<=i+root&&cur<q)tmp.pb(qry[cur]),cur++;
        solve(tmp);
    }
    for(int i=0;i<q;i++)cout<<out[i]<<'\n';
}

Compilation message (stderr)

poklon.cpp:32:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   32 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
poklon.cpp:38:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   38 | bool cmp(ppii a,ppii b){return a.f.s<b.f.s;}
      |                       ^
poklon.cpp:39:25: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   39 | void solve(vector<ppii>g){
      |                         ^
poklon.cpp:67:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   67 | int32_t main(){
      |              ^

• Subtask 1: 140 / 140