oj.uz

답안 #380282

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
380282 2021-03-20T20:34:39 Z nigus Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 1342 ms 49540 KB 
//
//Vi läser input på formen N, sen N rader med strängar (ordlistan), sen M, sen M rader med par med strängar P och Q. Ex:
//
//N
//s1
//s2
//s3
//...
//sN
//M
//P1 Q1
//P2 Q2
//P3 Q3
// ...
//PM QM
//


#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef long long ll;
typedef vector<long long> vl;
typedef vector<vector<long long>> vvl;
typedef pair<int, int> pii;
typedef vector<pair<int, int>> vpii;
typedef vector<vector<pair<int, int>>> vvpii;
typedef pair<long long, long long> pll;
typedef vector<pair<long long, long long>> vpll;
typedef vector<vector<pair<long long, long long>>> vvpll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, b) for(auto &a : b)
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define deb(x) cout << endl << #x << ": " << x << endl
#define deb2(x, y) cout << endl << #x << ": " << x << ", " << #y << ": " << y << endl
#define deb3(x, y, z) cout << endl << #x << ": " << x << ", " << #y << ": " << y << ", " << #z << ": " << z << endl
#define debP(p) cout << endl << #p << ": " << p.first << ", " << p.second << endl
#define debArr(x) cout << endl << #x << ": "; rep(abc, 0, x.size()) cout << x[abc] << " "
#define el cout << endl
#define sz(x) x.size()

//number &= ~(1UL << n);            -Turn off bit
//number |= (1UL << n);             -Turn on bit
//number ^= (1UL << n);             -Toggle bit
//bool on = (number & (1UL << n)    -whether the n-th (0-indexed) bit is on or off

//Fenwick-träd
struct FT {
	vector<ll> s;
	FT(int n) : s(n) {}
	void update(int pos, ll dif) { // a[pos] += dif
		for (; pos < sz(s); pos |= pos + 1) s[pos] += dif;
	}
	ll query(int pos) { // sum of values in [0, pos)
		ll res = 0;
		for (; pos > 0; pos &= pos - 1) res += s[pos-1];
		return res;
	}
	int lower_bound(ll sum) {// min pos st sum of [0, pos] >= sum
		// Returns n if no sum is >= sum, or -1 if empty sum is.
		if (sum <= 0) return -1;
		int pos = 0;
		for (int pw = 1 << 25; pw; pw >>= 1) {
			if (pos + pw <= sz(s) && s[pos + pw-1] < sum)
				pos += pw, sum -= s[pos-1];
		}
		return pos;
	}
};

int numbering = 0;
struct Item { // Vi sorterar queries och indexen som vi ska querya över. Detta är ett sätt att räkna ut antal tal i ett intervall < K
    bool isQuery, isAddition; //Om itemet är en query eller bara element, och om svaret på eventuell query ska + eller - på svaret
    int E; //Om itemet är ett element, så är detta värdet på elementet
    int L, R, K, I; //För query: L, R beskriver intervallet (inclusive),
    // K beskriver vilket för vilket tal vi queriar under (prioriteten), I är index på svaret som vi ska uppdatera efter denna query
    int number = numbering++;
    Item(bool isQuery, int E) : isQuery(isQuery), E(E) {};
    Item(bool isQuery, int L, int R, int K, int I, bool isAddition) : isQuery(isQuery), L(L), R(R), K(K), I(I), isAddition(isAddition) {};
};

bool comp(const Item& A, const Item& B) { //Jämför to-do-list items för sorteringen
    int pA = A.isQuery ? A.K : A.E;
    int pB = B.isQuery ? B.K : B.E;
    if (pA == pB) {
        if (A.isQuery && !B.isQuery) return true;
        if (!A.isQuery && B.isQuery) return false;
        return (A.number < B.number);
    }
    return pA < pB;
}

int N; //Antal ord
int M; //Antal queries
vs A; //Vektorn med alla ord sorterade i bokstavsordning
vs B; //Vektorn med alla ord baklänges sorterade i bokstavsordning
vector<Item> toDoList;
vi ftIndex;

vector<string> ps, qs;
unordered_set<ll> pref, suff;
const ll base = 128923;

unordered_map<string, pii> intervalsA;
unordered_map<string, pii> intervalsB;

void savePrefix(unordered_map<string, pii>& intervals, string& prefix, int index) {
    if (intervals.find(prefix) == intervals.end()) {
        intervals[prefix].first = index;
    }
    intervals[prefix].second = index;
}

void preCalculateIntervals() {
    rep(i, 0, N) { //Loopa igenom varje ord
        string current = "";
        ll h = 0;
        rep(j, 0, sz(A[i])) { //Loopa igenom alla möjliga prefix för ordet A[i]
            h *= base;
            h += A[i][j];
            current += A[i].at(j);
            if(pref.find(h) != pref.end())savePrefix(intervalsA, current, i); //Spara prefixet (om det är den första eller sista förekomsten)
        }
        current = "";
        h = 0;
        rep(j, 0, sz(B[i])) { //Gör samma med alla ord i B
            h *= base;
            h += B[i][j];
            current += B[i].at(j);
            if(suff.find(h) != suff.end())savePrefix(intervalsB, current, i);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> M;
    vector<pair<string, int>> B_andToA;
    rep(i, 0, N) { //Läs in alla ord, och bygg upp ordlistorna
        string ord; cin >> ord;
        A.pb(ord);
    }

    sort(all(A)); //Sortera ordlistan A

    rep(i, 0, N) {
        string ord = A[i];
        reverse(all(ord));
        B_andToA.pb(mp(ord, i));
    }
    sort(all(B_andToA)); //Sortera ordlistan B

    ftIndex.resize(N);
    rep(i, 0, sz(B_andToA)) {
        B.pb(B_andToA[i].first);
        ftIndex[i] = B_andToA[i].second; //Spara vilket index varje tal i fenwickträdet kommer ha, så vi kan uppdatera det snabbt
    }

    rep(c1,0,M){
        string P, Q; cin >> P >> Q;
        ps.push_back(P);
        qs.push_back(Q);
        ll h = 0;
        trav(ch, P){
            h *= base;
            h += ch;
        }
        pref.insert(h);
        h = 0;
        reverse(all(Q));
        trav(ch, Q){
            h *= base;
            h += ch;
        }
        suff.insert(h);
    }

    preCalculateIntervals();

    vi ans(M, 0);
    rep(i, 0, M) { //Lägg in alla queries i "to-do-listan"
        string P, Q; P = ps[i]; Q = qs[i];
        reverse(all(Q));
        if (intervalsA.find(P) == intervalsA.end() || intervalsB.find(Q) == intervalsB.end()) continue;
        pii intervalA = intervalsA[P];
        pii intervalB = intervalsB[Q];
        int LA = intervalA.first;
        int RA = intervalA.second;
        int LB = intervalB.first;
        int RB = intervalB.second;
        Item itemR(true, LA, RA, RB + 1, i, true);
        Item itemL(true, LA, RA, LB, i, false);
        toDoList.pb(itemR);
        toDoList.pb(itemL);
    }

    rep(i, 0, N) { //Lägg till alla index också, som vi ska querya efter i ordning
        Item item(false, i);
        toDoList.pb(item);
    }

    sort(all(toDoList), comp);

    FT ft(N);
    trav(item, toDoList) {
        if (item.isQuery) { //Om det vi ska göra nu är att hantera en query
            ll res = ft.query(item.R + 1) - ft.query(item.L);
            ans[item.I] += (1 - (2 * !item.isAddition)) * res;
        }else { //Om det vi ska göra nu är att lägga till ett till index
            int pos = ftIndex[item.E];
            ft.update(pos, 1);
        }
    }

    trav(a, ans) {
        cout << a << "\n";
    }
}

Compilation message

selling_rna.cpp: In member function 'void FT::update(int, ll)':
selling_rna.cpp:61:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |   for (; pos < sz(s); pos |= pos + 1) s[pos] += dif;
      |              ^
selling_rna.cpp: In member function 'int FT::lower_bound(ll)':
selling_rna.cpp:73:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |    if (pos + pw <= sz(s) && s[pos + pw-1] < sum)
      |                 ^
selling_rna.cpp: In constructor 'Item::Item(bool, int, int, int, int, bool)':
selling_rna.cpp:84:18: warning: 'Item::I' will be initialized after [-Wreorder]
   84 |     int L, R, K, I; //För query: L, R beskriver intervallet (inclusive),
      |                  ^
selling_rna.cpp:82:19: warning:   'bool Item::isAddition' [-Wreorder]
   82 |     bool isQuery, isAddition; //Om itemet är en query eller bara element, och om svaret på eventuell query ska + eller - på svaret
      |                   ^~~~~~~~~~
selling_rna.cpp:88:5: warning:   when initialized here [-Wreorder]
   88 |     Item(bool isQuery, int L, int R, int K, int I, bool isAddition) : isQuery(isQuery), L(L), R(R), K(K), I(I), isAddition(isAddition) {};
      |     ^~~~
selling_rna.cpp: In function 'void preCalculateIntervals()':
selling_rna.cpp:38:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 | #define rep(i, a, b) for(int i = a; i < (b); ++i)
      |                                       ^
selling_rna.cpp:127:9: note: in expansion of macro 'rep'
  127 |         rep(j, 0, sz(A[i])) { //Loopa igenom alla möjliga prefix för ordet A[i]
      |         ^~~
selling_rna.cpp:38:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 | #define rep(i, a, b) for(int i = a; i < (b); ++i)
      |                                       ^
selling_rna.cpp:135:9: note: in expansion of macro 'rep'
  135 |         rep(j, 0, sz(B[i])) { //Gör samma med alla ord i B
      |         ^~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:38:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::__cxx11::basic_string<char>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 | #define rep(i, a, b) for(int i = a; i < (b); ++i)
      |                                       ^
selling_rna.cpp:165:5: note: in expansion of macro 'rep'
  165 |     rep(i, 0, sz(B_andToA)) {
      |     ^~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 364 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 729 ms 12380 KB Output is correct
2 Correct 721 ms 14736 KB Output is correct
3 Correct 734 ms 14364 KB Output is correct
4 Correct 726 ms 14820 KB Output is correct
5 Correct 146 ms 12168 KB Output is correct
6 Correct 149 ms 12140 KB Output is correct
7 Correct 1342 ms 18132 KB Output is correct
8 Correct 222 ms 21316 KB Output is correct
9 Correct 190 ms 21984 KB Output is correct
10 Correct 338 ms 13060 KB Output is correct

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 102 ms 18396 KB Output is correct
2 Correct 70 ms 10100 KB Output is correct
3 Correct 87 ms 12600 KB Output is correct
4 Correct 72 ms 12512 KB Output is correct
5 Correct 70 ms 10080 KB Output is correct
6 Correct 90 ms 12600 KB Output is correct

Subtask #4
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 729 ms 12380 KB Output is correct
9 Correct 721 ms 14736 KB Output is correct
10 Correct 734 ms 14364 KB Output is correct
11 Correct 726 ms 14820 KB Output is correct
12 Correct 146 ms 12168 KB Output is correct
13 Correct 149 ms 12140 KB Output is correct
14 Correct 1342 ms 18132 KB Output is correct
15 Correct 222 ms 21316 KB Output is correct
16 Correct 190 ms 21984 KB Output is correct
17 Correct 338 ms 13060 KB Output is correct
18 Correct 102 ms 18396 KB Output is correct
19 Correct 70 ms 10100 KB Output is correct
20 Correct 87 ms 12600 KB Output is correct
21 Correct 72 ms 12512 KB Output is correct
22 Correct 70 ms 10080 KB Output is correct
23 Correct 90 ms 12600 KB Output is correct
24 Correct 437 ms 18072 KB Output is correct
25 Correct 318 ms 23184 KB Output is correct
26 Correct 575 ms 16032 KB Output is correct
27 Correct 447 ms 18228 KB Output is correct
28 Correct 530 ms 49540 KB Output is correct
29 Correct 288 ms 39908 KB Output is correct