Submission #941210

#	Time	Username	Problem	Language	Result	Execution time	Memory
941210		phamducminh	Poklon (COCI17_poklon)	C++17	0 / 140	6 ms	14752 KiB

poklon

//******************/
//*   I<3   C++    */
//*  I WANT ANY AC */
//* I LOVE PROGRAM!*/
//*IT'S INTERESTING*/
//* I LOVE PROGRAM!*/
//*  IN CONTESTS   */
//*   GET SCORE    */
//*    AC CODE     */
//*     LET'S      */
//*      GO        */
//*  Written by:   */
//*   Duc Minh     */






#include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <algorithm>
#include <string>
#include <queue>
#include <cctype>
#include <cstring>
#include <iomanip>
#include <deque>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>

using namespace std;
// using namespace __gnu_pbds;

#define  file(name)  freopen(name".inp", "r", stdin);\
                     freopen(name".out", "w", stdout);
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define TIME        (1.0 * clock() / CLOCKS_PER_SEC)
#define all(a)      a.begin(),a.end()
#define endl        "\n"
#define all1(a)     a+1,a+n+1
#define unordered_map  map
// #define push_back   emplace_back
// #define gcd(a,b)    __gcd(a,b);
// #define lcm(a,b)    (a*b)/gcd(a,b);

const long long INF = (long long)1e9;
const long long MOD = (long long)1e9+7;
const long long MODD = 2017; /// 998244353
const long long maxN = 5e5+9;
const int LOG = 18;
const int mlift = 58;


template<class A> inline int __lg(A &a) {  return static_cast<int>(log2(a));}
template<class A,class B> inline void add(A &a,B b) { a+=b;while (a>=MOD) a-=MOD;}
template<class A,class B> inline void minus(A &a,B b) { a-=b;while (a>=MOD) a-=MOD;while (a<0) a+=MOD;}






///--------------------------------


void solve();

signed main(){

    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    #ifndef ONLINE_JUDGE
        file("ducminh");
    #endif


    // file("BAI4");







    long long t;


    // cin >> t; 

    t=1;



    while (t--){




        solve();


    }





    cerr << "Time elapsed: " << TIME << "s.\n";
    cerr << "ducminh" << "\n";
    return 0;
}



///--------------------[PROBLEM SOLUTION]--------------------///







long long tree[maxN*4];
long long a[maxN],vt[maxN],b[maxN],n,q;

void buildtree(long long id, long long l, long long r){

    if (l==r){

        tree[id]=a[l];
        return;
    }

    long long m=(l+r)>>1;

    buildtree(id*2,l,m);
    buildtree(id*2+1,m+1,r);

    tree[id]=tree[id*2]+tree[id*2+1];


}


void updatetree(long long id, long long l, long long r, long long u, long long v, long long val){

    if (u>r || v<l) return;

    if (l==r){

        tree[id]+=val;
        return;

    }

    long long m=(l+r)>>1;

    updatetree(id*2,l,m,u,v,val);
    updatetree(id*2+1,m+1,r,u,v,val);

    tree[id]=tree[id*2]+tree[id*2+1];

}



long long gettree(long long id, long long l, long long r, long long u, long long v){


    if (u>r || v<l) return 0;

    if (u<=l && r<=v) return tree[id];

    long long m=(l+r)>>1;

    return gettree(id*2,l,m,u,v)+gettree(id*2+1,m+1,r,u,v);
}

vector<pair<long long,long long>> luu[500009];
long long ans[500009];
unordered_map<long long,vector<long long>> mm;

void solve(){


    cin >> n >> q;

    for (int i=1; i<=n; i++){
        cin >> a[i];
    }

    for (int i=1; i<=q; i++){
        int l,r;
        cin >> l >> r;

        luu[l].push_back({r,i});
    }


    for (int i=n; i>=1; i--){

        if (mm[a[i]].size()==1) updatetree(1,1,n,i,i,1);
        else{
            if (mm[a[i]].size()>1){
                int sz=mm[a[i]].size();
                updatetree(1,1,n,i,i,1);
                updatetree(1,1,n,mm[a[i]][sz-2],mm[a[i]][sz-2],-1);
                updatetree(1,1,n,mm[a[i]][sz-1],mm[a[i]][sz-1],-1);
            }
        }
        mm[a[i]].push_back(i);


        for (pair<int,int> x: luu[i]){
            if (x.first-i==0) ans[x.second]=0;
            else
            // cout << i << ' ' << x.first << ' ' << gettree(1,1,n,i,x.first) << "\n";
            ans[x.second]=max(0LL,gettree(1,1,n,i,x.first));
        }
    }


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




}

Compilation message (stderr)

poklon.cpp: In function 'int main()':
poklon.cpp:40:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 | #define  file(name)  freopen(name".inp", "r", stdin);\
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
poklon.cpp:78:9: note: in expansion of macro 'file'
   78 |         file("ducminh");
      |         ^~~~
poklon.cpp:41:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |                      freopen(name".out", "w", stdout);
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
poklon.cpp:78:9: note: in expansion of macro 'file'
   78 |         file("ducminh");
      |         ^~~~

• Subtask 1: 0 / 140