fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define MAX   400400
  3. #define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
  4. #define FORD(i,b,a) for (int i=(b),_a=(a);i>=_a;i=i-1)
  5. #define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
  6. #define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
  7. #define ALL(v) (v).begin(),(v).end()
  8. #define fi   first
  9. #define se   second
  10. #define MASK(i) (1LL<<(i))
  11. #define BIT(x,i) (((x)>>(i))&1)
  12. #define div   ___div
  13. #define next   ___next
  14. #define prev   ___prev
  15. #define left   ___left
  16. #define right   ___right
  17. #define __builtin_popcount __builtin_popcountll
  18. using namespace std;
  19. template<class X,class Y>
  20.     void minimize(X &x,const Y &y) {
  21.         if (x>y) x=y;
  22.     }
  23. template<class X,class Y>
  24.     void maximize(X &x,const Y &y) {
  25.         if (x<y) x=y;
  26.     }
  27. template<class T>
  28.     T Abs(const T &x) {
  29.         return (x<0?-x:x);
  30.     }
  31.  
  32. /* Author: Van Hanh Pham - skyvn97 */
  33.  
  34. /** END OF TEMPLATE - ACTUAL SOLUTION COMES HERE **/
  35.  
  36. char input[MAX];
  37. string readString(void) {
  38.     scanf("%s", input);
  39.     return string(input);
  40. }
  41.  
  42. struct Node {
  43.      int cnt;
  44.      bool haveString;
  45.      Node* child[26];
  46.  
  47.      Node() {
  48.         cnt = 0;
  49.         haveString = false;
  50.         REP(i, 26) child[i] = NULL;
  51.      }
  52. };
  53.  
  54. struct Query {
  55.     int pos, answer, id;
  56.     string perm;
  57.     Query() {
  58.         pos = answer = id = 0;
  59.     }
  60.     void input(int id) {
  61.         this->id = id;
  62.         scanf("%d", &pos);
  63.         perm = readString();
  64.     }
  65. };
  66. /*** LOOK AT MY CODE. MY CODE IS AMAZING :D ***/
  67.  
  68. Node* root;
  69. Query queries[MAX];
  70. vector<int> queriesAt[MAX];
  71. int numStrings, numQueries;
  72. int numPrefix[MAX];
  73. string str[MAX];
  74.  
  75. void init(void) {
  76.     scanf("%d", &numStrings);
  77.     FOR(i, 1, numStrings) str[i] = readString();
  78.     scanf("%d", &numQueries);
  79.     FOR(i, 1, numQueries) queries[i].input(i);
  80. }
  81.  
  82. int addString(const string &s) {
  83.     int res = 0;
  84.     Node *p = root;
  85.     FORE(it, s) {
  86.         if (p->child[*it - 'a'] == NULL) p->child[*it - 'a'] = new Node();
  87.         p = p->child[*it - 'a'];
  88.         p->cnt++;
  89.         if (p->haveString) res++;
  90.     }
  91.     p->haveString = true;
  92.     return res;
  93. }
  94.  
  95. int cnt[30][30];
  96. void answerQueries(int strID) {
  97.     memset(cnt, 0, sizeof cnt);
  98.  
  99.     Node *p = root;
  100.     FORE(it, str[strID]) {
  101.         int j = *it - 'a';
  102.         REP(i, 26) if (i != j && p->child[i] != NULL) cnt[j][i] += p->child[i]->cnt;
  103.         p = p->child[j];
  104.     }
  105.  
  106.     FORE(it, queriesAt[strID]) {
  107.         int id = *it;
  108.         queries[id].answer = numPrefix[strID] + 1;
  109.         string &perm = queries[id].perm;
  110.         REP(i, 26) FOR(j, i + 1, 25) queries[id].answer += cnt[perm[j] - 'a'][perm[i] - 'a'];
  111.     }
  112. }
  113.  
  114. bool CompLength(const int &a, const int &b) {
  115.     return str[a].size() < str[b].size();
  116. }
  117. void process(void) {
  118.     root = new Node();
  119.     vector<int> strIDs;
  120.     FOR(i, 1, numStrings) strIDs.push_back(i);
  121.     sort(ALL(strIDs), CompLength);
  122.     FORE(it, strIDs) numPrefix[*it] = addString(str[*it]);
  123.  
  124.  
  125.     FOR(i, 1, numQueries) queriesAt[queries[i].pos].push_back(i);
  126.     FOR(i, 1, numStrings) answerQueries(i);
  127.     FOR(i, 1, numQueries) printf("%d\n", queries[i].answer);
  128. }
  129.  
  130. int main(void) {
  131.     init();
  132.     process();
  133.     return 0;
  134. }
Success #stdin #stdout 0.02s 44340KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/46ONEE
Solution to problem: Lexicographical Disorder, AtCoder - CODE FESTIVAL 2016 round B, problem E
Link: https://a...content-available-to-author-only...r.jp/contests/code-festival-2016-qualb/tasks/codefestival_2016_qualB_e
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!