oj.uz

답안 #941305

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
941305 2024-03-08T13:24:03 Z phamducminh Poklon (COCI17_poklon) C++17
84 / 140
 5000 ms 12164 KB 
//******************/
//*   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 = 2024; /// 998244353
const long long maxN = 5e5+9;
const int LOG = sqrt(maxN);
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);



    // 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]--------------------///




int a[maxN],cur=0,n,q,ans[maxN],block;
vector<int> b;
unordered_map<int,int> mm;
int _left=1, _right=0;

struct Query {
    int l, r, pos;
} queries[maxN];



bool cmp(Query x, Query y) {
    return (make_pair(x.l / LOG, x.r) < make_pair(y.l / LOG, y.r));
}



void add(int pos) {
    if(pos == 0) return;
    int x = a[pos];
    if(mm[x] == 2) cur--;
    mm[x]++;
    if(mm[x] == 2) cur++;
}

void erase(int pos) {
    if(pos == 0) return;
    int x = a[pos];
    if(mm[x] == 2) cur--;
    mm[x]--;
    if(mm[x] == 2) cur++;
}



void mo(int i){

    while (_left<queries[i].l){
        erase(_left);
        _left++;
    }
    while (_left>queries[i].l){
        add(_left-1);
        _left--;
    }
    while (_right>queries[i].r){
        erase(_right);
        _right--;
    }
    while (_right<queries[i].r){
        add(_right+1);
        _right++;
    } 
}



void solve(){


    cin >> n >> q;

    block=(int)sqrt(n);

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

    sort(all(b));
    b.resize(unique(all(b)) - b.begin());
 
    for(int i = 1; i <= n; i++)
        a[i] = lower_bound(all(b), a[i]) - b.begin() + 1;

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

        queries[i].pos=i;
    }


    sort(queries+1,queries+q+1,cmp);


    for (int i=1; i<=q; i++){

        mo(i);
        ans[queries[i].pos]=cur;
    }


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




}

Compilation message

poklon.cpp: In function 'void solve()':
poklon.cpp:199:13: warning: unused variable 'l' [-Wunused-variable]
  199 |         int l,r;
      |             ^
poklon.cpp:199:15: warning: unused variable 'r' [-Wunused-variable]
  199 |         int l,r;
      |               ^

Subtask #1
84.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 3 ms 4444 KB Output is correct
3 Correct 8 ms 4444 KB Output is correct
4 Correct 40 ms 4680 KB Output is correct
5 Correct 1465 ms 7304 KB Output is correct
6 Correct 1796 ms 7308 KB Output is correct
7 Execution timed out 5088 ms 9824 KB Time limit exceeded
8 Execution timed out 5040 ms 10608 KB Time limit exceeded
9 Execution timed out 5009 ms 11372 KB Time limit exceeded
10 Execution timed out 5046 ms 12164 KB Time limit exceeded