Submission #617430

#	Time	Username	Problem	Language	Result	Execution time	Memory
617430		patrikpavic2	Misspelling (JOI22_misspelling)	C++17	100 / 100	657 ms	124364 KiB

misspelling

#include <cstdio>
#include <set>
#include <algorithm>
#include <vector>

#define PB push_back

using namespace std;

typedef long long ll;

const int N = 5e5 + 500;
const int ALP = 30;
const int MOD = 1e9 + 7;

inline int add(int A, int B){
	if(A + B >= MOD)
		return A + B - MOD;
	return A + B;
}

inline int sub(int A, int B){
	if(A - B < 0)
		return A - B + MOD;
	return A - B;
}

inline int mul(int A, int B){
	return (ll)A * B % MOD;
}

int n, q, A[N], B[N], P[N][ALP], gran[N][2];
vector < int > ubac[N][2];
set < int > S[2];

int main(){
	scanf("%d%d", &n, &q);
	for(int i = 0;i < q;i++){
		scanf("%d%d", A + i, B + i);
		ubac[max(A[i], B[i])][A[i] < B[i]].PB(min(A[i], B[i]));
	}
	S[0].insert(0); S[1].insert(0);
	for(int i = n;i >= 1;i--){
		for(int k = 0;k < 2;k++){
			for(int x : ubac[i][k]) S[k].insert(x);
			while(*S[k].rbegin() == i)
				S[k].erase(*S[k].rbegin());
		}
		gran[i][0] = *S[0].rbegin();
		gran[i][1] = *S[1].rbegin();	
	}
	for(int j = 0;j < 26;j++) P[1][j] = 1;
	for(int i = 2;i <= n;i++){
		int sve = max(gran[i][0], gran[i][1]);
		//printf("%d %d\n", ubac[i][0], ubac[i][1]);
		int uk = 0;
		for(int j = 0;j < 26;j++)
			uk = add(uk, sub(P[i - 1][j], P[sve][j]));		
		for(int j = 0;j < 26;j++)
			P[i][j] = sub(uk, sub(P[i - 1][j], P[sve][j]));
		if(gran[i][0] > gran[i][1]){ // > 
			uk = 0;
			for(int j = 25;j >= 0;j--){
				P[i][j] = add(P[i][j], uk);
				uk = add(uk, sub(P[gran[i][0]][j], P[gran[i][1]][j]));
			}
		}
		else if(gran[i][0] < gran[i][1]){ // <
			uk = 0;
			for(int j = 0;j < 26;j++){
				P[i][j] = add(P[i][j], uk);
				uk = add(uk, sub(P[gran[i][1]][j], P[gran[i][0]][j]));
			}		
		}
		for(int j = 0;j < 26;j++){
			P[i][j] = add(P[i - 1][j], P[i][j]);
		}
	}
	int uk = 0;
	for(int j = 0;j < 26;j++)
		uk = add(uk, P[n][j]);
	printf("%d\n", uk);
	return 0;
}

Compilation message (stderr)

misspelling.cpp: In function 'int main()':
misspelling.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |  scanf("%d%d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~
misspelling.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |   scanf("%d%d", A + i, B + i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 20 / 20
• Subtask 3: 29 / 29
• Subtask 4: 32 / 32
• Subtask 5: 11 / 11