oj.uz

Submission #144507

# Submission time Handle Problem Language Result Execution time Memory
144507 2019-08-17T00:40:31 Z 12tqian Lottery (CEOI18_lot) C++14
35 / 100
 594 ms 4604 KB 
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

const double PI = 4 * atan(1);

#define sz(x) (int)(x).size()
#define ll long long
#define ld long double
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pii pair <int, int>
#define vi vector<int>
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define vpi vector<pair<int, int>>
#define vpd vector<pair<double, double>>
#define pd pair<double, double>

#define f0r(i,a) for(int i=0;i<a;i++)
#define f1r(i,a,b) for(int i=a;i<b;i++)
#define trav(a, x) for (auto& a : x)

template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) {
  cout << "["; for(int i = 0; i < v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";
}

void fast_io(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
}
void io(string taskname){
    string fin = taskname + ".in";
    string fout = taskname + ".out";
    const char* FIN = fin.c_str();
    const char* FOUT = fout.c_str();
    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);
    fast_io();
}
const int MAX = 1e4 + 5;
const int MAXQ = 1e2 + 5;
vector<short int> a;
int n, l;
int cnt[MAX][MAXQ];
int bucket[MAX];
vi queries;
vi sorted;
int um[MAX];
int main(){
    fast_io();
    scanf("%d %d", &n, &l);
    f0r(i, n){
        short int ai;
        scanf("%d", &ai);
        a.eb(ai);
    }


    int q;
    scanf("%d", &q);
    //cout << q << endl;
    set<int> s;
    f0r(tmp, q){
        int k;
        scanf("%d", &k);
        queries.eb(k);
        sorted.eb(k);
        s.insert(k);
    }
    for(auto x: s) sorted.eb(x);
    //sort(all(sorted));
    f0r(i, sz(sorted)){
        um[sorted[i]] = i;
        assert(sorted[i]<MAX);
    }
    f0r(i, n){
        bool isTrue = true;
        for(int j = sz(sorted) - 1; j>= 0; j--){
            if(i<= sorted[j]){
                bucket[i] = j;
                isTrue = false;
                continue;
            }
        }
        if(isTrue) bucket[i] = MAXQ -1;
    }
    int cur = 0;
    f1r(d,1, n){
        int val = 0;
        f0r(i, n-l+1){
            int j = i +d;
            if(j>=n-l+1)continue;
            if(i == 0){
                f0r(it, l){
                    val += (a[i+it]!=a[j+it]);
                }
            }
            else{
                if(i>0 && j>0) val -= (a[i-1]!=a[j-1]);
                val += (a[i + l-1] != a[j + l-1]);
            }
            cnt[i][bucket[val]]++;
            cnt[j][bucket[val]]++;
        }
    }
    f0r(i, n-l+1){
        f1r(j,1, MAXQ){
            cnt[i][j] += cnt[i][j-1];
        }
    }
    f0r(tmp, q){
        f0r(i, n-l + 1){
            printf("%d ", cnt[i][um[queries[tmp]]] );
        }
        printf("\n");
    }
    return 0;
}

Compilation message

lot.cpp:1:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/stack:200000000")
 
lot.cpp: In function 'int main()':
lot.cpp:70:24: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'short int*' [-Wformat=]
         scanf("%d", &ai);
                     ~~~^
lot.cpp:103:9: warning: unused variable 'cur' [-Wunused-variable]
     int cur = 0;
         ^~~
lot.cpp: In function 'void io(std::__cxx11::string)':
lot.cpp:52:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen(FIN, "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~
lot.cpp:53:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen(FOUT, "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~
lot.cpp: In function 'int main()':
lot.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &l);
     ~~~~~^~~~~~~~~~~~~~~~~
lot.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &ai);
         ~~~~~^~~~~~~~~~~
lot.cpp:76:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q);
     ~~~~~^~~~~~~~~~
lot.cpp:81:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &k);
         ~~~~~^~~~~~~~~~

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 575 ms 4600 KB Output is correct
2 Correct 581 ms 4592 KB Output is correct
3 Correct 584 ms 4604 KB Output is correct
4 Correct 554 ms 4508 KB Output is correct
5 Correct 165 ms 2424 KB Output is correct
6 Correct 519 ms 4216 KB Output is correct
7 Correct 167 ms 2556 KB Output is correct
8 Correct 307 ms 3364 KB Output is correct
9 Correct 546 ms 4472 KB Output is correct
10 Correct 565 ms 4600 KB Output is correct
11 Correct 25 ms 1144 KB Output is correct
12 Correct 324 ms 3320 KB Output is correct
13 Correct 235 ms 2808 KB Output is correct
14 Correct 222 ms 3064 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 575 ms 4600 KB Output is correct
2 Correct 581 ms 4592 KB Output is correct
3 Correct 584 ms 4604 KB Output is correct
4 Correct 554 ms 4508 KB Output is correct
5 Correct 165 ms 2424 KB Output is correct
6 Correct 519 ms 4216 KB Output is correct
7 Correct 167 ms 2556 KB Output is correct
8 Correct 307 ms 3364 KB Output is correct
9 Correct 546 ms 4472 KB Output is correct
10 Correct 565 ms 4600 KB Output is correct
11 Correct 25 ms 1144 KB Output is correct
12 Correct 324 ms 3320 KB Output is correct
13 Correct 235 ms 2808 KB Output is correct
14 Correct 222 ms 3064 KB Output is correct
15 Correct 546 ms 4576 KB Output is correct
16 Correct 480 ms 4216 KB Output is correct
17 Correct 594 ms 4600 KB Output is correct
18 Correct 571 ms 4600 KB Output is correct
19 Correct 576 ms 4572 KB Output is correct
20 Correct 573 ms 4600 KB Output is correct
21 Correct 567 ms 4600 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -