oj.uz

Submission #144505

# Submission time Handle Problem Language Result Execution time Memory
144505 2019-08-17T00:36:13 Z 12tqian Lottery (CEOI18_lot) C++14
60 / 100
 708 ms 4728 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][105];
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;
    f0r(tmp, q){
        int k;
        scanf("%d", &k);
        queries.eb(k);
        sorted.eb(k);
    }
    sort(all(sorted));
    f0r(i, sz(sorted)){
        um[sorted[i]] = i;
    }
    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:99: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:80:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &k);
         ~~~~~^~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 4 ms 504 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 4 ms 504 KB Output is correct
13 Correct 32 ms 1244 KB Output is correct
14 Incorrect 19 ms 964 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 682 ms 4600 KB Output is correct
2 Correct 661 ms 4728 KB Output is correct
3 Correct 663 ms 4728 KB Output is correct
4 Correct 638 ms 4728 KB Output is correct
5 Correct 197 ms 2552 KB Output is correct
6 Correct 586 ms 4504 KB Output is correct
7 Correct 193 ms 2652 KB Output is correct
8 Correct 345 ms 3576 KB Output is correct
9 Correct 636 ms 4572 KB Output is correct
10 Correct 651 ms 4728 KB Output is correct
11 Correct 30 ms 1272 KB Output is correct
12 Correct 334 ms 3448 KB Output is correct
13 Correct 255 ms 3064 KB Output is correct
14 Correct 254 ms 2936 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 682 ms 4600 KB Output is correct
2 Correct 661 ms 4728 KB Output is correct
3 Correct 663 ms 4728 KB Output is correct
4 Correct 638 ms 4728 KB Output is correct
5 Correct 197 ms 2552 KB Output is correct
6 Correct 586 ms 4504 KB Output is correct
7 Correct 193 ms 2652 KB Output is correct
8 Correct 345 ms 3576 KB Output is correct
9 Correct 636 ms 4572 KB Output is correct
10 Correct 651 ms 4728 KB Output is correct
11 Correct 30 ms 1272 KB Output is correct
12 Correct 334 ms 3448 KB Output is correct
13 Correct 255 ms 3064 KB Output is correct
14 Correct 254 ms 2936 KB Output is correct
15 Correct 636 ms 4488 KB Output is correct
16 Correct 571 ms 4344 KB Output is correct
17 Correct 708 ms 4728 KB Output is correct
18 Correct 665 ms 4728 KB Output is correct
19 Correct 649 ms 4644 KB Output is correct
20 Correct 656 ms 4644 KB Output is correct
21 Correct 661 ms 4600 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 4 ms 504 KB Output is correct
13 Correct 32 ms 1244 KB Output is correct
14 Incorrect 19 ms 964 KB Output isn't correct
15 Halted 0 ms 0 KB -