JACK2021's blog

By JACK2021, history, 18 months ago, In English

look at this code:(It is for at abc281_e)

include <bits/stdc++.h>

using namespace std;

define p_qu priority_queue

define p_qu_less priority_queue<int, vector, greater >

define C_in(a,n) for(int i=0;i<n;i++) cin>>a[i]

define C_out(a,n) for(int i=0;i<n;i++) cout<<a[i]<<" "

define SUM(a,n,sum) sum[0]=a[0];for(int i=1;i<n;i++) sum[i]=sum[i-1]+a[i];

define SUM2(a,n,m,sum) sum[0][0]=a[0][0]; for(int i=0;i<n;i++) for(int j=0;j<m;j++) sum[i][j]=(i!=0?sum[i-1][j]:0)+(j!=0?sum[i][j-1]:0)+a[i][j]-(i!=0 && j!=0?sum[i-1][j-1]:0)

define all(a) a.begin(),a.end()

define l_b lower_bound

define u_b upper_bound

define pb push_back

define max_3(a,b,c) max(max(a,b),c)

define max_4(a,b,c,d) max(a,max_3(b,c,d))

define min_3(a,b,c) min(min(a,b),c)

define min_4(a,b,c,d) min(a,min_3(b,c,d))

define zero(a) memset(a, 0, sizeof(a))

define msit multiset::iterator

define setit set::iterator

define int long long

const int N=500005;

const int MAX=(1<<31)-1;

multiset s,t;

int n,m,k;

int a[N];

int ans;

signed main()

{

//freopen("input.txt","r",stdin);

//freopen("output.txt","w",stdout);

cin>>n>>m>>k;

C_in(a,n);

for(int i=0;i<m;i++)

{

    t.insert(a[i]);

}

for(int i=0;i<k;i++)

{

    s.insert(*t.begin());

    ans+=*t.begin();

    t.erase(t.begin());

}

cout<<ans<<" ";

for(int i=1;i<=n-m;i++)

{

    bool cc=false;

    if( a[i-1]>=*t.begin())

    {

       t.erase(t.find(a[i-1]));

    }

    else

    {

       s.erase(s.find(a[i-1]));

       ans-=a[i-1];

       cc=true;

    }

    int now=a[i+m-1];

    t.insert(now);

    if(cc)

    {

       s.insert(*t.begin());

       ans+=*t.begin();

       t.erase(t.begin());

    }

    else

    {

       if(*t.begin()<*s.rbegin())

       {

         ans-=*s.rbegin();

         ans+=*t.begin();

         msit j=s.end();

         j--;

         t.insert(*j);

         s.erase(j);

         msit i=t.begin();

         t.erase(i);

         s.insert(*i);

       }

    }

    cout<<ans<<" ";

}

return 0;

}

and my friend's code:

include <bits/stdc++.h>

using namespace std;

int a[200005];

multiset L, R;

int main() {

int n, m, k;

scanf("%d %d %d", &n, &m, &k);

for (int i = 0; i < n; i++) {

    scanf("%d", &a[i]);

}

// 先把所有的插到 L 中

long long ans = 0;

for (int i = 0; i < m; i++) {

    L.insert(a[i]);

    ans += a[i];

}

// 再决出前 k 个

for (int i = 0; i < m &mdash; k; i++) {

    int x = *(--L.end());

    L.erase(L.find(x));

    R.insert(x);

    ans -= x;

}

printf("%lld ", ans);

// 滑动窗口

for (int i = 1; i <= n &mdash; m; i++) {

    // 前一个不需要的

    int x = a[i &mdash; 1];

    if (x <= (*(--L.end()))) {

       L.erase(L.find(x));

       ans -= x;

    } else {

       R.erase(R.find(x));

    }

    // 后一个需要的

    int y = a[i + m &mdash; 1];

    if (y < (*(--L.end())) || (y == (*(--L.end())) && L.size() == k &mdash; 1)) {

       L.insert(y);

       ans += y;

    } else {

       R.insert(y);

    }

    // R 补给 L

    if (L.size() <= k &mdash; 1) {

       while (L.size() < k) {

         int z = *R.begin();

         R.erase(R.begin());

         L.insert(z);

         ans += z;

       }

    }

    // L 补给 R

    if (L.size() >= k + 1) {

       while (L.size() > k) {

         int z = *(--L.end());

         L.erase(L.find(z));

         R.insert(z);

         ans -= z;
       }

    }

    printf("%lld ", ans);
}

return 0;

}

They're both not true. But one is RE one is TLE.We made the same mistake. We both not write"!empty()".But why one is RE and one is TLE.my friend tell me that RE and TLE are both Unaccepted

Full text and comments »

  • Vote: I like it
  • -17
  • Vote: I do not like it