oj.uz

Submission #548568

# Submission time Handle Problem Language Result Execution time Memory
548568 2022-04-13T20:11:19 Z NAHDI Selling RNA Strands (JOI16_selling_rna) C++14
10 / 100
 1500 ms 11132 KB 
#include <bits/stdc++.h>
using namespace std;

using vi = vector<int>;
using vii = vector<vi>;
using vs = vector<string>;
using vss = vector<vs>;
using vb = vector<bool>;
using vbb  = vector<vb>;
using ii = pair<int, int>;
using vpi = vector<ii>;
using vpii = vector<vpi>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using table = unordered_map<unsigned long, int>;
using pll = pair<ll,ll>;
using vpl = vector<pll>;
using vpll = vector<vpl>;

#define f first
#define s second

#define forn(i, n) for(int i = 0; i < n; i++)
#define fore(i, a, b) for(int i = a; i <= b; i++)
#define for1n(i, n) for(int i = 1; i <= n; i++)
#define rof(i, n) for(int i = n-1; i >= 0; i--)
#define rofe(i, a, b) for(int i = b; i >= a; i--)
#define all(x) x.begin(), x.end()
#define dsc(type) greater<type>

#define Flag cout << "Reached here.\n"
#define FASTIO ios::sync_with_stdio(0); cin.tie(0);

#define pb push_back
#define pbb pop_back
#define sz size
#define rsz resize
#define rsv reserve
#define ins insert

#define lb(a, val) lower_bound(all(a), val);
#define ub(a, val) upper_bound(all(a), val);

#define onec(x) __builtin_popcount(x)
#define end0(x) __builtin_clz(x)
#define beg0(x) __builtin_ctz(x)

#define MAX 1000000000
#define MIN -MAX

#define mod 1000000007LL

#define clr(x, y) memset(x, y, sizeof(x))

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

int dx[] = {0, 1, -1, 0};
int dy[] = {1, 0, 0, -1};

ll binpow(ll a, ll b) {
    a %= mod;
    ll res = 1;
    while (b > 0) {
        if (b & 1) res *= a, res %= mod;
        a *= a, a %= mod;
        b >>= 1;
    }
    return res;
}

vi fct(ll n) {
    vi fac;
    while(n%2 == 0) n /= 2, fac.pb(2);
    for(int i = 3; i * i <= n; i += 2) 
        while(n%i == 0) fac.pb(i), n /= i;
    if(n > 1) fac.pb(n);
    return fac;
}

ll gcd(ll a, ll b) {
   if (b == 0) return a;
   return gcd(b, a % b);
}

ll lcm(ll a, ll b) {
    return (a*b) / gcd(a, b);
}

#define maxN 
#define mxSM 

void task2(int n, int m, vs& s, vs& p, vs& q) {
    vector<pair<string, int>> rev(n);
    sort(all(s));
    forn(i, n) {
        rev[i] = {s[i], i};
        reverse(all(rev[i].f));
    }
    sort(all(rev));

    forn(i, m) {
        int cnt=  0;
        vi ok(5001);
        int l1 = lower_bound(all(s), p[i]) - s.begin();
        p[i][p[i].sz()-1]++;
        int r1 = lower_bound(all(s), p[i]) - s.begin();
        reverse(all(q[i]));
        int l2 = lower_bound(all(rev), pair<string, int>{q[i], -1}) - rev.begin();
        q[i][q[i].sz()-1]++;
        int r2 = lower_bound(all(rev), pair<string, int>{q[i], -1}) - rev.begin();
        
        //cout << l1 << ' ' << r1 << '\n';
        //cout << l2 << ' ' << r2 << '\n';

        for(int j = l1; j < r1; j++) {
            //cout << s[j] << '\n';
            ok[j]++;
        }
        //cout << '\n';
        for(int j = l2; j < r2; j++) {
            reverse(all(rev[j].f));
            //cout << rev[j].f << '\n';
            reverse(all(rev[j].f));
            ok[rev[j].s]++;
        }
        forn(i, ok.sz()) if(ok[i] == 2) cnt++;
        cout << cnt << '\n';
    }

}

void solve() {
    int n, m;
    cin >> n >> m;
    vs s(n);
    forn(i, n) cin >> s[i];
    vs p(m), q(m);
    forn(i, m) cin >> p[i] >> q[i];
    

    if(n <= 5000 && m <= 5000) {
        task2(n, m, s, p, q);
        return;
    }
}

int main() {
    FASTIO;
    solve();
}

Compilation message

selling_rna.cpp: In function 'void task2(int, int, vs&, vs&, vs&)':
selling_rna.cpp:24:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 | #define forn(i, n) for(int i = 0; i < n; i++)
......
  128 |         forn(i, ok.sz()) if(ok[i] == 2) cnt++;
      |              ~~~~~~~~~~              
selling_rna.cpp:128:9: note: in expansion of macro 'forn'
  128 |         forn(i, ok.sz()) if(ok[i] == 2) cnt++;
      |         ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 673 ms 10732 KB Output is correct
2 Execution timed out 1555 ms 11132 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 5456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 673 ms 10732 KB Output is correct
9 Execution timed out 1555 ms 11132 KB Time limit exceeded
10 Halted 0 ms 0 KB -