priy1712's blog

By priy1712, history, 10 months ago, In English
#include <bits/stdc++.h>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#define ci(n) cin>>n
#define co(n) cout<<n
#define nl '\n'
#define r0 return 0
#define LLMAX LLONG_MAX
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define printstr(s) for(int i=0;i<(int)s.size();i++) { cout<<s[i];}
typedef std::pair<int, int> pp;
typedef long long ll;
typedef std::vector<ll> vl;
typedef std::vector<std::pair<int, int>> vp;
typedef std::vector<int> vi;
typedef std::unordered_map<int, int> unmap;
typedef std::unordered_set<int> unset;
typedef std::unordered_set<char> unsetc;
using namespace std;


const int max_size = 100005;
vector<bitset<1005>> b(max_size);//matrix of bitsets.
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // unordered_map<ll, ll> mp;
    // mp.reserve(1024);
    // mp.max_load_factor(0.25);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ll n, q;
    ci(n); ci(q);
    for (int i = 1; i <= n; ++i)
    {
        ll k;
        ci(k);
        for (int j = 0; j < k; ++j)
        {
            ll item; ci(item);
            b[i].set(item);//in stock.
        }
    }
    while (q--)
    {
        int curquery;
        ci(curquery);
        // co(curquery); co(nl);
        if (curquery == 1) //have to replace items in a shop
        {
            ll shop; ci(shop);
            ll k;
            ci(k);
            // const int curk = k;
            bitset < 1005> items;
            items.reset();
            for (int i = 0; i < k; ++i)
            {
                int x; ci(x);
                items[x] = 1;
                b[shop] &= items;//the common ones will stay 1.
                //others will become 0.
            }
        }
        else
        {
            ll l, r; ci(l); ci(r);
            ll k; ci(k);
            bitset < 1005> items;
            items.reset();
            for (int i = 0; i < k ; ++i)
            {
                int x; ci(x);
                items[x] = 1;//items he is willing to sell. the shopkeepers
                //will buy only if their intersection with the chef is 0.
                //that is , no common items
            }
            bitset<1005> cur;
            cur.reset();
            ll res = 0;
            for (int i = l; i <= r; ++i)
            {
                cur = b[i];
                cur &= items;
                if (cur.count() == 0)
                {
                    res++;
                }
                cur.reset();
            }
            co(res); co(nl);
        }
    }
    r0;
}

The above code compiles fine and gives the correct output too on my local machine but its TLEIng when I submit it to the OJ, could anyone help me out? thanks. The problem statement : https://www.codechef.com/problems/T30?tab=statement

UPD: it works fine on codeforces custom invocation too.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by priy1712 (previous revision, new revision, compare).

»
10 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Never mind.

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    did you find any error?

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Not, just your algo has bad time complexity.

      • »
        »
        »
        »
        10 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        could you suggest optimizations , I cant really see where to optimize further , some of the nested loops i cant help its because of the input format

        • »
          »
          »
          »
          »
          10 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I do not see any ways to optimize the solution to get it accepted. Try to reorganize the data. Maybe a map like item -> set of shops where it is missing would help.