제출 #380282

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
380282		nigus	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	1342 ms	49540 KiB

selling_rna

//
//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";
    }
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40