QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#22728#2135. How Many Strings Are Lessasoul#Compile Error//C++204.2kb2022-03-10 15:45:552022-05-18 04:13:09

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-18 04:13:09]
  • 评测
查看
  • [2022-03-10 15:45:55]
  • 提交

answer

#include<bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i ++)
#define per(i, r, l) for(int i = (r); i >= (l); i --)
#define trv(i, u, v) for(int i = head[u], v = e[i].to; i; v = e[i = e[i].nxt].to)
#define fi first
#define se second
#define all(s) s.begin(), s.end()
#define sz(s) (int)(s.size())
#define lb(s) ((s) & -(s))
#define pb push_back
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
mt19937_64 hua(time(0));
template<typename T> inline bool chkmx(T &x, T y) {return x < y ? x = y, 1 : 0;}
template<typename T> inline bool chkmn(T &x, T y) {return y < x ? x = y, 1 : 0;}
template<int T> using A = array<int, T>;

inline int read() {
	int x = 0, f = 1; char c = getchar();
	for(; !isdigit(c); c = getchar()) if(c == '-')  f = 0;
	for(; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	return f ? x : -x;
}
const int maxn = 1e6;
const int mxlg = 20;
int n, q;
char s[maxn + 5];
struct Node {
	int l, r, c, st, ed;
}stk[maxn + 5];
int curans, tp;
struct Trie {
	int nxt[maxn + 5][26], gogo[maxn + 5][mxlg + 1], val[maxn + 5][mxlg + 5], end[maxn + 5];
	int siz[maxn + 5], fa[maxn + 5], pre[maxn + 5][26];
	int ncnt = 1;
	void ins(char *s) {
		int len = strlen(s + 1);
		int p = 1;
		rep(i, 1, len) {
//			cout << s[i];
			if(!nxt[p][s[i] - 'a']) nxt[p][s[i] - 'a'] = ++ ncnt;
			p = nxt[p][s[i] - 'a'];
			siz[p] ++;
		}
		end[p] ++;
//		cout << '\n';
	}
	void dfs(int u) {
		rep(i, 0, 25) if(nxt[u][i]) fa[nxt[u][i]] = u, dfs(nxt[u][i]);
		int cur = 0;
		rep(j, 0, 25) {
			if(nxt[u][j]) {
//				cout << u << "-->" << nxt[u][j] <<  ' ' << (char)(j + 'a') << '\n';
				cur += end[nxt[u][j]];
				pre[u][j] = cur;
				val[nxt[u][j]][0] = pre[nxt[u][j]][j];
//				if(nxt[u][j] == 14) {
//					cout << val[nxt[u][j]][0] << "???\n";
//				}
				if(u == 14) {
//					cout << pre[u][j] << ' ' << end[nxt[u][j]] << '\n';
				}
				cur += siz[nxt[u][j]] - end[nxt[u][j]];
				gogo[nxt[u][j]][0] = nxt[nxt[u][j]][j];
			}
			else {
				pre[u][j] = cur;
//				if(u == 8) {
//					cout << j << ' '<< cur << "qwqeqweqw\n";
//				}
			}
		}
//		cout << u << ":" << gogo[u][0] << ' ' << gogo[u][1] << ' ' << val[u][0] << ' ' << val[u][1] << '\n';
	}
	void dfs2(int u) {
		rep(i, 0, 25) if(nxt[u][i]) dfs2(nxt[u][i]);
		rep(j, 1, mxlg) {
//			if(u == 14) cout << val[u][j - 1] << '\n'; 
			gogo[u][j] = gogo[gogo[u][j - 1]][j - 1];
			val[u][j] = val[u][j - 1] + val[gogo[u][j - 1]][j - 1];
		}
	}
	void init() {
		
		dfs(1);
		dfs2(1);
	}
	P calc(int u, int c, int len) {
//		cout << u << ' ' << c << ' ' << len << "----\n";
		if(!u || !nxt[u][c]) return {0, pre[u][c]};
		int p = nxt[u][c], ans = pre[u][c]; len --;
//		cout << p << ' ' << len << ' ' << val[p][0] << ' ' << ans << '\n';
		per(i, mxlg, 0) if(len >> i & 1){
			ans += val[p][i];
			p = gogo[p][i];
		}
		return {p, ans};
	}
}ds;
void push(int l, int r, int c) {
//	cout << l << ' '<< r << ' ' << c<< '\n';
	P cur = ds.calc(stk[tp].ed, c, r - l + 1);
	stk[++ tp] = {l, r, c, stk[tp - 1].ed, cur.fi};
	curans += cur.se;
}
void pop() {
	P cur = ds.calc(stk[tp].st, stk[tp].c, stk[tp].r - stk[tp].l + 1);
	curans -= cur.se;
	tp --;
}
int main() {
//	freopen("in.txt", "r", stdin);
	ios::sync_with_stdio(false);
	cin >> n >> q;
	cin >> s + 1;
	rep(i, 1, n) {
		static char str[maxn + 5];
		cin >> str + 1;
		ds.ins(str);
	}
	ds.init();
//	cout << ds.calc(7, 'n' - 'a', 4).se << '\n';
//	return 0;
//	cout << ds.calc(8, 1, 10).se << '\n';
//	return 0;
	stk[0].ed = 1; 
	int lens = strlen(s + 1);
	rep(i, 1, lens) {
		push(i, i, s[i] - 'a');
	}
	cout << curans << '\n';
	rep(i, 1, q) {
		static char str[maxn + 5];
		static int p;
		cin >> p >> str + 1;
		while(stk[tp].r >= p) pop();
		if(stk[tp].r != p - 1) {
			push(stk[tp].r + 1, p - 1, stk[tp + 1].c);
		}
		push(p, lens, str[1] - 'a');
		int ret = 0;
//		rep(i, 1, tp) ret += ds.calc(stk[i].st, stk[i].c, stk[i].r - stk[i].l + 1).se;
		cout << curans - ds.end[stk[tp].ed] << '\n';
//		rep(i, 1, tp) {
//			cout << stk[i].l << ' ' << stk[i].r << ' ' << stk[i].c << ' ' << stk[i].st << ' ' << stk[i].ed << ' ' << ds.calc(stk[i].st, stk[i].c, stk[i].r - stk[i].l + 1).se << '\n';;
//		}
	}
	return 0;
}
Source code, Language: C++20

Details 

answer.code: In function ‘int main()’:
answer.code:117:13: error: no match for ‘operator>>’ (operand types are ‘std::istream’ {aka ‘std::basic_istream<char>’} and ‘char*’)
  117 |         cin >> s + 1;
      |         ~~~ ^~ ~~~~~
      |         |        |
      |         |        char*
      |         std::istream {aka std::basic_istream<char>}
In file included from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from answer.code:1:
/usr/include/c++/11/istream:168:7: note: candidate: ‘std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(bool&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]’ (near match)
  168 |       operator>>(bool& __n)
      |       ^~~~~~~~
/usr/include/c++/11/istream:168:7: note:   conversion of argument 1 would be ill-formed:
answer.code:117:18: error: cannot bind non-const lvalue reference of type ‘bool&’ to a value of type ‘char*’
  117 |         cin >> s + 1;
      |                ~~^~~
In file included from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from answer.code:1:
/usr/include/c++/11/istream:172:7: note: candidate: ‘std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(short int&) [with _CharT = char; _Traits = std::char_traits<char>]’ (near match)
  172 |       operator>>(short& __n);
      |       ^~~~~~~~
/usr/include/c++/11/istream:172:7: note:   conversion of argument 1 would be ill-formed:
answer.code:117:18: error: invalid conversion from ‘char*’ to ‘short int’ [-fpermissive]
  117 |         cin >> s + 1;
      |                ~~^~~
      |                  |
      |                  char*
answer.code:117:18: error: cannot bind rvalue ‘(short int)(((char*)(& s)) + 1)’ to ‘short int&’
In file included from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from answer.code:1:
/usr/include/c++/11/istream:175:7: note: candidate: ‘std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(short unsigned int&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]’ (near match)
  175 |       operator>>(unsigned short& __n)
      |       ^~~~~~~~
/usr/include/c++/11/istream:175:7: note:   conversion of argument 1 would be ill-formed:
answer.code:117:18: error: invalid conversion from ‘char*’ to ‘short unsigned int’ [-fpermissive]
  117 |         cin >> s + 1;
      |                ~~^~~
      |                  |
      |                  char*
answer.code:117:18: error: cannot bind rvalue ‘(short unsigned int)(((char*)(& s)) + 1)’ to ‘short unsigned int&’
In file included from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from answer.code:1:
/usr/include/c++/11/istream:179:7: note: candidate: ‘std::basic_istream<_CharT, _Traits>& std::basic_istream<_CharT, _Traits>::operator>>(int&) [with _CharT = char; _Traits = std::char_traits<char>]’ (near match)
  179 |       operator>>(int& __n);
      |       ^~~~~~~~
/usr/include/c++/11/istream:179:7: note:   conversion of argument 1 would be ill-formed:
answer.code:117:18: error: invalid conversion from ‘char*’ to ‘int’ [-fpermissive]
  117 |         cin >> s + 1;
      |                ~~^~~
      |                  |
      |                  char*
answer.code:117:18: error: cannot bind rvalue ‘(int)(((char*)(& s)) + 1)’ to ‘int&’
In file included from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from answer.code:1:
/usr/include/c++/11/istream:182:7: note: candidate: ‘std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(unsigned int&) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_istream<_CharT, _Traits>::__istream_type = std::basic_istream<char>]’ (near match)
  182 |       operator>>(unsigned int& __n)
      |       ^~~~~~~~
/usr/include/c++/11/istream:182:7: note:   conversion of argument 1 would be ill-formed:
answer.code:117:18: error: invalid conv...
English 繁體中文 简体中文

Server Time: 2025-01-20 19:57:15 | OpenSource Project