제출 #1016900

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

selling_rna

#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
#define ll long long
#define int long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii, int> ipii;
const int MAXN = 1e5+10;
const int MAXA = 110;
const int INF = 1e18+10;
const int LOG = 19;
const int MOD = 1e9+7;
const int SQRT = 450;
const vector<int> NOL = {};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const vector<int> dx = {1, -1, 0, 0};
const vector<int> dy = {0, 0, 1, -1};
void chmx(int &a, int b){ a = max(a, b); }

int n, k, ans[MAXN];
string p[MAXN], q[MAXN];
vector <pair<string,int>> vec;
string te;

struct seg {
    int cnt, idx;
    seg* a[4];
    void bd(int nw){
        if(a[nw] == NULL){
            a[nw] = new seg(); a[nw]->idx = idx+1; a[nw]->cnt = 0;
        }
    }
    void upd(){
        // if(idx!=-1) cout << te[idx] << ' '<< te << " te\n";
        cnt++;
        // cout << idx << ' ' << te <<"pp\n";
        if(idx+1==te.size()) return;
        if(te[idx+1] == 'A'){
            bd(0); a[0]->upd();
        } else if(te[idx+1] == 'C'){
            bd(1); a[1]->upd();
        } else if(te[idx+1] == 'U'){
            bd(2); a[2]->upd();
        } else if(te[idx+1] == 'G'){
            bd(3); a[3]->upd();
        }
    }
    int que(){
        if(idx+1==te.size()) return cnt;
        if(te[idx+1] == 'A'){
            bd(0); return a[0]->que();
        } else if(te[idx+1] == 'C'){
            bd(1); return a[1]->que();
        } else if(te[idx+1] == 'U'){
            bd(2); return a[2]->que();
        } else if(te[idx+1] == 'G'){
            bd(3); return a[3]->que();
        }
        assert(false);
    }
} *A;

signed main(){
    // ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    A = new seg(); A->idx = -1;
    cin >> n >> k;
    for(int i=1; i<=n; i++){
        string s; cin >> s; vec.pb({s, 0});
    }
    for(int i=1; i<=k; i++){
        cin >> p[i] >> q[i];
        for(int j=0; j<q[i].size()/2; j++) swap(q[i][j], q[i][q[i].size()-j-1]);

        vec.pb({p[i], -i});
        string te = p[i]; te += 'Z';
        vec.pb({te, i});
    }
    sort(vec.begin(), vec.end());
    // for(auto in : vec) cout << in.fi << ' ' << in.se << " vec\n";

    for(auto in : vec){
        if(in.se==0){
            te = in.fi;
            for(int i=0; i<te.size()/2; i++) swap(te[i], te[(int)te.size()-i-1]);
                // cout << te << " te\n";
            A->upd();
        // cout << A->a[1]->cnt << " cnt\n";
        } else if(in.se < 0){
            int id = -in.se, idx = 0;
            te = q[id];
            int ret = A->que();
            ans[id] -= ret;
            // cout << ret << ' ' << id << "id min\n";

        } else {
            int id = in.se, idx = 0;
            te = q[id];
            int ret = A->que();
            ans[id] += ret;
            // cout << ret << ' ' << id << "id plus\n";
        }
    }
    for(int i=1; i<=k; i++) cout << ans[i] << '\n';
}

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

selling_rna.cpp: In member function 'void seg::upd()':
selling_rna.cpp:44:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |         if(idx+1==te.size()) return;
      |            ~~~~~^~~~~~~~~~~
selling_rna.cpp: In member function 'long long int seg::que()':
selling_rna.cpp:56:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         if(idx+1==te.size()) return cnt;
      |            ~~~~~^~~~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:79:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         for(int j=0; j<q[i].size()/2; j++) swap(q[i][j], q[i][q[i].size()-j-1]);
      |                      ~^~~~~~~~~~~~~~
selling_rna.cpp:91:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |             for(int i=0; i<te.size()/2; i++) swap(te[i], te[(int)te.size()-i-1]);
      |                          ~^~~~~~~~~~~~
selling_rna.cpp:96:30: warning: unused variable 'idx' [-Wunused-variable]
   96 |             int id = -in.se, idx = 0;
      |                              ^~~
selling_rna.cpp:103:29: warning: unused variable 'idx' [-Wunused-variable]
  103 |             int id = in.se, idx = 0;
      |                             ^~~

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40