Submission #612109

#	Time	Username	Problem	Language	Result	Execution time	Memory
612109		Andyvanh1	Lottery (CEOI18_lot)	C++14	100 / 100	2234 ms	8524 KiB

lot

#include <bits/stdc++.h>

using namespace std;

#define vt vector
#define pb push_back
#define all(x) x.begin(),x.end()
#define FORR1(x) for(int i = 0; i < (x); i++)
#define FORR2(j,x) for(int (j) = 0; (j) < (x); (j)++)
#define f first
#define s second

typedef vt<int> vi;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;

map<int,vi> mp;
map<int,int> dic;
int pp[10005];
int sz[10005];
int cst[10005];
int ans[10005][103];


int find(int x){
    return (x==pp[x] ? x : pp[x] = find(pp[x]));
}

void join(int a, int b){
    if(find(a)==find(b))return;
    int u = find(a), v = find(b);
    if(sz[u]>sz[v])swap(u,v);
    pp[u] = v;
    sz[v]+=sz[u];
}

void solve(){
    int n, l;
    cin>>n>>l;
    vi arr(n);
    FORR1(n)cin>>arr[i];
    FORR1(n){
        pp[i] = i;
        sz[i] = 1;
    }
    int q;
    cin>>q;
    vi qs;
    FORR1(q){
        int r;
        cin>>r;
        qs.pb(r);
        dic[r] = i;

    }

    int k = n-l+2;



    FORR1(n){
        if(mp.find(arr[i])==mp.end()){
            mp[arr[i]] = {i};
        }else{
            mp[arr[i]].pb(i);
        }
    }

    for(auto& e: mp) {

        int m = e.s.size();

       for(int i = 1; i < m; i++){
           join(e.s[i],e.s[i-1]);
       }

    }

    vi cur(n);
    FORR1(n)cur[i] = 0;
    FORR1(l){
        for(int j = n-1; j > 0; j--){
            cur[j] = cur[j-1];
        }
        cur[0] = 0;
        FORR2(j,n){
            if(find(j)==find(i)){
                cur[j]++;
            }
        }
    }

    FORR1(n-l+1){
        FORR2(j,l+1)cst[j] = 0;
        for(int j = l-1; j < n; j++)cst[l-cur[j]]++;
        for(int j = 1; j <= l; j++){
            cst[j]+=cst[j-1];
        }
        FORR2(j,q){
            ans[i][j] = cst[qs[j]];
        }
        if(i==n-l)break;
        for(int j = n-1; j > 0; j--){
            cur[j] = cur[j-1];
        }
        cur[0] = 0;
        FORR2(j,n){
            if(find(j)==find(l+i)){
                cur[j]++;
            }
        }
        FORR2(j,n-l){
            if(find(j)==find(i)){
                cur[j+l]--;
            }

        }
        

    }
    FORR1(q){
        FORR2(j,n-l+1)cout<<ans[j][i]-1<<' ';
        cout<<'\n';
    }




}


int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    solve();
    return 0;
}

Compilation message (stderr)

lot.cpp: In function 'void solve()':
lot.cpp:9:28: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    9 | #define FORR2(j,x) for(int (j) = 0; (j) < (x); (j)++)
      |                            ^
lot.cpp:87:9: note: in expansion of macro 'FORR2'
   87 |         FORR2(j,n){
      |         ^~~~~
lot.cpp:9:28: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    9 | #define FORR2(j,x) for(int (j) = 0; (j) < (x); (j)++)
      |                            ^
lot.cpp:95:9: note: in expansion of macro 'FORR2'
   95 |         FORR2(j,l+1)cst[j] = 0;
      |         ^~~~~
lot.cpp:9:28: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    9 | #define FORR2(j,x) for(int (j) = 0; (j) < (x); (j)++)
      |                            ^
lot.cpp:100:9: note: in expansion of macro 'FORR2'
  100 |         FORR2(j,q){
      |         ^~~~~
lot.cpp:9:28: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    9 | #define FORR2(j,x) for(int (j) = 0; (j) < (x); (j)++)
      |                            ^
lot.cpp:108:9: note: in expansion of macro 'FORR2'
  108 |         FORR2(j,n){
      |         ^~~~~
lot.cpp:9:28: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    9 | #define FORR2(j,x) for(int (j) = 0; (j) < (x); (j)++)
      |                            ^
lot.cpp:113:9: note: in expansion of macro 'FORR2'
  113 |         FORR2(j,n-l){
      |         ^~~~~
lot.cpp:9:28: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    9 | #define FORR2(j,x) for(int (j) = 0; (j) < (x); (j)++)
      |                            ^
lot.cpp:123:9: note: in expansion of macro 'FORR2'
  123 |         FORR2(j,n-l+1)cout<<ans[j][i]-1<<' ';
      |         ^~~~~
lot.cpp:58:9: warning: unused variable 'k' [-Wunused-variable]
   58 |     int k = n-l+2;
      |         ^

• Subtask 1: 25 / 25
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20